THANK YOU, Sandy! I wished I found this before the "5-hour phone call" (it was longer, actually). AT&T sent me to Blackberry, who sent me to Yahoo and they all fingered each other, and didn't fix the issue. ARGH!!!
I am glad other people are experiencing this and I will wait for a resolution. Meanwhile, I HATE deleting emails off my phone that I've already deleted on my laptop. Such a waste of time. Aren't we all spoiled?