I've had it quite a bit with Rogers lately. I just hit cancel - no need to enter my pw.
There are quite a few similar complaints in the Apple forums, and a lot of people have tried things like you've done, some with similarly no success. I'm using Tiger and having the issue occasionally - others are seeing it in Leopard too.
Someone at ehmac.com suggested deleting the Library->Keychains folder and then re-enter your Mail passwords, but I think that would delete
all your passwords and that might not be the result you desire. Apparently it stopped the Mail problem though.
I think it depends a bit on what is actually wrong. For me, I think it's a brief network interruption when Mail is contacting the mail server (I have it set to do this every 5 minutes.), especially since I don't actually have to enter my PW in order to get the mail going forward, if I simply cancel the request for the PW. See:
http://parasiilonmac.blogspot.com/2006/10/...sword-even.html It appears that it is a long-standing issue - here's a thread from 2004:
http://forums.macosxhints.com/archive/index.php/t-29263.html