I would add that this occurs also on OpenBSD, so it may be an upstream problem with GMail or with Alpine or both.

(epiphany loses all form field data when going back a page, thus is a bad mix with this bug tracking tool)

alpine cannot undo marking a message as deleted. 

steps:

log into gmail using alpine
press 'd' to delete a message
press 'u' to undelete

alpine says the message is no longer marked for deletion, but the deleted flag remains and when deleted messages are flushed the message is gone for good

I would expect the message to lose the deleted flag when using 'u'   Undeleting using * doesn't help either.

$ apt-cache policy alpine
alpine:
  Installed: 1.10+dfsg-3
  Candidate: 1.10+dfsg-3
  Version table:
 *** 1.10+dfsg-3 0
        500 http://archive.gnewsense.org metad/main Packages
        100 /var/lib/dpkg/status

$ lsb_release -rd
Description: gNewSense GNU/Linux 3.0 (metad)
Release: 3.0


the problem may be with alpine itself or in the interaction between gmail and alpine.  I get the same problem on alpine in openbsd-current (4.6) on i386