I have the very same problem with my paid Yahoo account. The fact that it doesn't work as expected doesn't necessarily mean the bug is with the Nexus One: it could also be Yahoo not working as expected. I find that I get an error when I sync and then immediately after I check my mailbox in a browser. I need to refresh the page sever times in order to clear the error.
I will test the Mail app with another POP mailbox and see if I get the same errors.