I'm having the same problem on my curve (yahoo and gmail not working). Was on the phone with a rep for about 30 minutes last night and she did an update. An hour later I had the same problem. This morning it took about 2 hours for the yahoo mail to sync. Got a call back tonight and they've done something because the deleted emails came off the handheld. But looks like its off again.
Go to the “Setup” folder. Click on Email Settings. Remove then re-add the Yahoo! Mail account. Then hit the BlackBerry button, and choose “Service Books”, then “Send Service Books”. Pull the battery. This may fix the problem.