Gmail marking everything as spam + scam

Excuse me if I'm asking basic questions but I'm a noob at email marketing and hitting a dead end. Every test email I send is marked as spam by gmail. I've tried searching for answers but almost every search I do revolves around how to prevent spam rather than prevent being flagged as spam. And for the relevant information I have found, I don't think I'm doing anything that would get me flagged as spam.

I created accounts with several companies that offer free accounts for small emailers. I settled on Mailkitchen because it was the only one that my personal email host (Rackspace) didn't mark as spam.

Getting through Rackspace is nice but for obvious reasons it's important that I am not flagged as spam by gmail so I can use a little help.

Not only are all my emails being marked as spam they are also getting flagged with "Be careful with this message. Similar messages were used to steal people's personal information. Unless you trust the sender, don't click links or reply with personal information." WTH!

I tried using four different domains as the sender address. From one of those domains I've never even sent email before let alone any spam. The other two domains have only been used for direct interaction with clients, I've never sent bulk email or spam from those accounts either. The fourth is strictly used as my personal email account, no commercial emails are ever sent from it. Same result every time, marked as junk and flagged as a possible scam.

First question, is Mailkitchen legitimate or is everything from them going to get flagged as spam?

Second question is does it matter who the domain itself is hosted with? All four domains I tested with are hosted by websitesource.com. If other people are sending spam from websitesource.com could that affect me even though I'm using a (hopefully) legitimate bulk marketing service? Would hosting my websites with another company help?

(As a point of clarification, the personal email I mentioned has a web page hosted by websitesource but all email goest through rackspace.)

Not sure what else I could be doing wrong. There is plenty of copy in the email and there are only five photos so I don't think I over did it with graphics. There is no ALL CAPS screaming. There is one link back to my website and one mailto: link. I haven't broken any of the obvious rules to get flagged as spam.

As a second test I cleared out the entire email and just sent a message of "This is legitimate. I like cheese" and the subject was "I like cheese." Same result, flagged as spam with the scam warning.

I doubt it makes a difference but my ISP is Time Warner so that's who's IP my computer would be associated with.

Can anyone help shed light on this? Especially why Google is flagging me as a possible phisher when I'm sending an email that just says I like cheese. I'm thinking the problem is Mailkitchen.

Thanks in advance for any light you can shed on this. This is so frustrating. I'm a noob but I'm a quick learner!