Have this problem as well. message *** not available on server.

Only on one of my gmail accounts (the one I use). Not on the other. Tried everything (that I could think of), googlemail username..
Imported imap google cert manually. updated ca-certs.. Reinstalled modest, nokiamessaging. Full reflash.. Nothing works.

My feeling (just a guess mind you) is the problem is, as is mentioned several times on this thread, on gmails side and no amount of tinkering will get my email account working working with a N900.