I'm creating an application that needs to send emails on behalf of a users' email address. On my current shared hosting (Bluehost) you cannot use email addresses from another domain. I was wondering what hosting/server set up I need to do this?
I have come across similar issues from Blue Host, You can send email on behalf of some email address but that will be like an alias.
For doing this you can use Mandril mail service or any other transactional email services.
They will digitally sign the emails so that they have less chance to reach spam.
To avoid misuse of such services, they have rules and time limits. But they are normal for an average user, as long as you do not send marketing bulk emails. You are good to go with Mandril email services.
Get their free PHP API from http://mandrill.com/
There are many other transactional email services, select what suits best for you.