Developing a website - want to avoid spam issues

Hey all-

I am having a new website developed (receiving bids right now for it).

I've had a few built over the past few years and with every single one of them it seems emails sent always end up in people spam folders (if the receive them at all - lots of times, not even delivered). And, I promise, no spamming going on - they are ecommerce sites that try to send their receipts. I don't even send newsletters in fear of being labeled a spammer.

I've tried serveral different hosting companies on shared servers and VPS, etc - to no avail.

Well, now this new site I am launching uses email very heavily where a user signs up on the site and specifies a friends email addresses to receive the mail. No more mailing past that, it's a one time thing - and their friend is the one providing the address wanting to send it to them.

This time, I want to go about it the right way and hire the right developers that can make it so mail is deliverable. I know there is no full-proof method, but some pointers would help.

I'd like to hear people's thoughts, here are some random questions of the bat:

-Can anyone recommend a good VPS company that has reliability in it's outgoing mail?

-Does it matter if phpsendmail is what's responsible for sending the mail? What about SMTP? (Not even sure the difference really)

-Is there any way to contact companies like Hotmail, Yahoo, etc. to prove we don't spam?

-Does it matter what email address it is saying it's being sent from (ie, could it say it's being sent from that users email, or would it need to say from the server it originates from)

I'd like to hear from people's experience any pointers to look for in the developer before I shell out serious cash. If the emails don't make it, the site is dead in the water.

Thanks so much, I really do appreciate it!