I can confirm that this is a giant pain in the ass. I use a non-standard address scheme (instead of the plus character as a tagged-address delimiter, I use the qmail approach, a dash character), so I can't easily move my domain to GMail. I occasionally end up in spam folders for reasons I can't discern, despite years of puzzling and discussion with a number of experts.

The especially frustrating thing is that there's no way to find out why you've been binned. Even my friends who work at Google can't find out for me, much less get me whitelisted.