About SPAM and the address-book-based blasts, I am afraid that Sara is correct. Every social network (Facebook, Myspace, Twitter, LinkedIn, Plaxo, and so on) has some capability to search your address book. As long as the user uploading knows that they are uploading, it isn't hugely unreasonable. And frankly, it is not practical to define SPAM as any email the recipient doesn't want to get. So while we don't have to like it, we can't say that it is outside the norms.
So, Sara, I answer the question with the following stipulations. Unless you accept these conditions, you do not have permission to use my advice ;-)
1- You only send an email ONCE per address, and take no response as an OPT-OUT.
2- You have an easy, one click opt-out readily accessible and linked in every blast.
3- You don't sell or share addresses or other personal info.
Now, to the advice ..
The source server is not likely a huge component of why your emails are getting flagged. Emails from known bad IPs and domains are typically not accepted by the destination ISPs rather than put into junk mail folders.
More likely, your emails look like spam. As to making them not look like spam, I can only give very general suggestions .. not too many links, valid return email address that matches the sending domain, avoid all caps, spelling errors and the various taboo words.
The server and mail service itself should also be setup properly .. reverse DNS, valid MX records, etc. There is extensive info on this site about that kind of configuration.
If the 500 messages/hour is a real problem, Google Apps might not have those limits, I don't know. Google Apps might also have other mail-related terms that will impact your business. I would check, and if it doesn't, go with it. If that doesn't work, rolling your own SMTP server is the only solution. VPS may work, but the provider might have anti-bulk-mail terms as well. You may have to suck it up and get your own hardware and rent rackspace and bandwidth.