It sounds as if your account may have been hacked and the 'hacker' in question has removed all trace of the sent e-mail from your online account.
From what you have described, I believe that your phone automatically stores copies of all sent/received e-mails locally (like most other smartphones do), regardless of whether or not they have been deleted from your online account. Therefore, if your phone had downloaded a copy of the sent e-mail before said 'hacker' had removed all trace of the e-mail, that would explain why it appears to have been sent from your phone rather than from your online account. Think of it as a misconception, if you like.
My advice would be to change your password once again as it sounds very suspicious indeed. Make sure that you never give your password to anybody, regardless of who they are.
You should also observe your account (activity) for the next week to see if anything suspicious has happened, and if not, then that should hopefully have solved the problem.