Hey BBLLLP:
I just figured this out, so I hope the solution is what you need. Re: your incoming mail, it's definitely a server issue
I have multiple devices and run 3 IMAP accounts through my apple mail. Once I upgraded my operating system/switched to iCloud, all of my sent messages on my devices (iPad and iPhone) disappeared. I would send an email from one device, but they did not show up when I needed to refer to them later. It was like they disappeared all together-very bizarre! After a call to AppleCare and a few hours of troubleshooting on my own, this is what I found.
In order to get your sent messages on the server, in each account you need to do the following (if you haven't already):
On your iPad:
Settings>Mail, Contacts, Calendars>Accounts>Choose your IMAP account>Advanced>Mailbox Behaviors>On the Server>Sent Messages.
For some odd reason, the default is set to ON MY iPad on ON MY iPhone once someone migrates to iCloud/Upgrades their operating system. It's easy to overlook.
On your iPhone:
Settings>Mail, Contacts, Calendars>Accounts>Choose your IMAP account>Advanced>Mailbox Behaviors>On the Server>Sent Messages. (Basically the same thing)
Apple told me to delete and recreate all of my IMAP accounts, but it seemed like it could have been an easier fix than that.
I'm not saying this will fix EVERYBODY's issue, but it certainly fixed mine. iCloud and Lion changed the default settings and it's not very obvious on how to fix it.
I hope this helps!
*Good Luck*