Yup, Gmail red flags IP. I have tried to get a criteria from them, but basically I was told if this happens, once a percentage of users mark the email as "not spam" your IP will go through again. I asked what percentage, no reply. :-(
I switched my main IP, which can't always be done (I understand) but that's how I got past it.
I would install my sendmail wrapper and watch for spam through scripts. (Posting it today to tips and tricks session, as it has worked a week under normal load without a huge cpu strain)