I've been using Mail for a long while with POP accounts. Recently I decided to stop using POP and switch all my accounts to IMAP. I simply disabled my POP accounts (not deleted at all yet) and set up the IMAP ones. Everything worked perfectly until I decided to move important messages from my Mac to the IMAP accounts (you do ithis in the same way as if you where moving messages between different mailboxes). The problem was that moving messages wasn't reliable -- sometimes messages got uploaded, while other times they became grayed out, but nothing happened.
After trying several things, including moving them one-by-one (which didn't work either), I found that rebuilding my local mailboxes seems to fix the problem -- as I write this, Mail has uploaded (moved) 350 of 870 messages without any problems.
As rebuilding is a per-mailbox thing, I've had to rebuild each local mailbox. I'm guessing that this problem comes from the fact that I've been moving my mailboxes around between four machines in the last year.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20081108142653907