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?