Just thought I'd write a note to say like Michael, I am experiencing the same problems again. From your experience it sounds like I have to either have patience and hope it resolves itself, or use autoforward to another address.
Yes. If you can access your email via webmail there is obviously nothing wrong with your password so it is pointless changing it and it can cause more problems than it solves. The best advice, other than to use different email provider is to do nothing other than wait.