This is going to depend a great deal on what about the messages you're sending gets them marked as spam. Google's documentation suggests that it's the app engine that actually does the SMTP, so there might be some other google app engine app that someone's marked as spam and your sending IP (which happens to be the same) is getting tarred with the same brush, or it might be something about the content of your messages. Many big mail providers give you some way to determine how 'spammy' they'll think a particular message will be; perhaps you could get information that way?
Another option is the standard 'be careful to add [some address] to your safe senders list if you want to get email from us!' warning in your app.