Could there be a common root to this issue, and that the phone stop syncing emails when the "low storage" warning comes on? No more incoming or outgoing emails, not even the manual "come on darn phone get my message" button does it. For me the warning kicks in around 14.85 MB (hit it so many times).
