Mail.app and multiple copies of emails

Follow these steps:

1. Open Mail and delete each of the conflicting accounts. Close Mail.
2. Go to ~/Library/Mail/ and make sure any IMAP-username123@imap.gmail.com folder has been deleted. If there is any such folder left, delete it now.
3. Open Mail and create one of the accounts and let Mail load your messages. Close Mail.
4. Go to ~/Library/Mail/ and verify that a folder called IMAP-username123@imap.gmail.com has been created.
5. Open ~/Library/Preferences/com.apple.mail.plist. If you have installed Xcode, this file will open with Property List Editor. Otherwise you can download a free trial of PlistEdit Pro to open this file. Using a plain text editor with .plist files is more difficult.
6. With the .plist file open, click the disclosure triangle for MailAccounts. Here you will find Item 0, Item 1, etc.
7. If you click the disclosure triangle for each of the Item headings, you will find that one of them has the value username123@gmail.com or username123@company.com for the AccountName key, depending on which account you created in step 3.
8. Change the value for AccountPath for this Item so that the path will not collide with that of the next account you are to create.
9. Save and close the .plist file.
10. Open Mail and let it reload your messages. Close Mail.
11. Go to ~/Library/Mail/ and verify that a folder with the path value you provided in step 8 has been created. Delete the old folder called IMAP-username123@imap.gmail.com.
12. Open Mail and create the remaining account normally and let Mail load your messages.

Under the View menu, check Hide Deleted Messages. That way, messages marked for deletion are no longer shown, and will be processed the next sync (like they used too).

It is possible you activated it unintentionally (it's just a ⌘+L away on the keyboard).