I also use gmail, but combined with offlineimap and dovecot, so that both modest and alpine only ever talk to dovecot.

So far I have never noticed any problem such as the one reported here.

Note that the "Message (title) not available on the server" as reported on the first post happens (AFAIK) when you are too quickly notified of a new message (e.g. with Nokia Messaging, which I used for a long time in the past) and *then* Google applies whatever filter it makes it move to another folder. When modest then tries to fetch the message, it's not there anymore.