OK lets try and get things sorted...
1. Ensure you have the correct "incoming and outgoing" details entered and in particular the settings in the Outgoing Mail server (SMTP) section reflects that the 'Use only this server' tick box is checked.
It is very important that your IMAP account only uses the "dedicated server from your Internet mailbox account provider". There is a hidden "edit" menu here that needs to be checked and for you to confirm the settings are as your provider settings.
I for example have a few GMX accounts. They are fantastic and are superb on IMAP.
Some times (don't ask me why) settings get changed. I had the problem after changing to Lion but after fiddling around and ensuring every thing was sound I then discovered an issue.
Key Chains.....
I suggest that you delete the keys relevant to your respective email accounts and do not enter the passwords in the Mail 'Account Information' window where you can see the list of accounts on intial set up of an account.
Now, if you can and aren't going to loose any sensitive mails, start from scratch as you would normally do but omit the " Enter password" section.
When you enable or connect for the fist time the pop up window will as you for a password and it wil give you the option to "Save password in Keychain" .....tick the box and you should be connected.
This section is a "Maybe"....
Now if you have another programme such as Outlook (which I have) and you need to use it as well then in the key chain where the new key has been lodged you can open it and select on Access control.
Therein you will find an icon of the programme that is using that key. You can add another application to it as well if you wish. Once done you see a window asking you to confirm. Click Yes.
Any how you should be working now. I also suggest you only add one mail box at a time. Set your first one to sync every 15 minutes. annd 30 minutes later add 2nd mailbox. I only suggest this as it allows you to concentrate on one thing at a time. Of course you can hit "Get Mail" any time to test as well.
Give it a go and report back..
Michael