You should definitely start changing your passwords though, because the wallet changes were confirmed via email, meaning the person has/had access to your email. The wallet was not locked.
I read thru the Support link and see how the address lock works but I don't see anything on how the email lock works, i.e., once locked can it be changed and how?
Email locks are generally not removed because generally an account is compromised via a compromised email (as in the case above). So sending a message from the locked address doesn't prove anything in many cases. A signed message from the wallet on the account is sometimes able to reverse an email lock, if the wallet used to sign the message has been on the account for a reasonable length of time (multiple payouts already processed to that address). It's examined on a case by case basis.