I am having the same problem.  I changed my password on my desktop but could still see email on my phone (including new mail post-password-change).  I then revoked access for the phone and sent another test message and I got *that* one too.

The scenario I'm concerned about is a lost/stolen phone, so "do such-and-such on the phone to force a reset" isn't interesting.  How do I prevent the phone from retaining access to my Google account when I don't want it to?