I don't want to start trying to fix your email issues in this post, but I do suggest that your problems can be addressed. Gmail in particular is difficult to setup correctly in any email client. It's non-standard IMAP.
As to the emails that were supposedly deleted, I have found that when I used MailTabPro for Gmail, it failed to delete all my messages even when I moved to the Trash.
FYI...Deleting a message in your browser will not delete the message. It simply moves it from Inbox to All Mail. To really delete, you have to move the message to the Trash.
See this article on using Gmail in Outlook. I go over the basics of how Gmail works and how to make the correct setting in your browser. Once you clean up your labels, see the second article on how to use Gmail in Apple Mail starting with OS X Mavericks.
Connect Outlook for Mac 2011 to Gmail’s IMAP service
Use Gmail with Mavericks Mail
(Fair disclosure: Needhelp4Mac & OfficeforMacHelp are my site. I may receive some form of compensation, financial or otherwise, from links on my site.)