Mac mail issues

Please help, I have recently changed servers and it has caused me a whole load of hassles with my mail......

I moved all of my mail into different 'on my mac' folders, we made a folder called 'old sent' and moved all sent mail into that....so I have all my mail saved...... so I delete the old mail accounts....

Now, I am sending and receiving mail normally.......

But, other weird things are happening.....

I use the search facility on mail all the time as have thousands of business emails.....

I have emails come up with the search facility that I cannot see anywhere else! When searching you have the headings; From/Subject/date received/rank/Mailbox......

In the Mailbox section, there now seems to be a mailbox called 'All mail' which is saving a copy of every single email, even if it has been moved to trash, it will have 1 copy of the original email and then 1 copy of that same email in trash......

In that same Mailbox section, I also now seem to have a mailbox called 'Sent mail' but that mail that was sent was deleted, so what is this 'Sent mail' mailbox?

So basically as a test, I sent a test email to my private email address...... I then back in my mac mail, I deleted the sent message...... then deleted the trash...... so in theory the message should be gone...... but when I search for 'testing' (the title of the test email) 2 emails appear one in the ?all mail' mailbox and 1 in the 'Sent mail' box.......

Am confused....

But I need to sort this asap before I start sending more emails, as using the search from now on will be a nightmare!

Any ideas?

 

I've been researching on the net.... could it have anything to do with gmail?