Generally MX (Mail eXchanger) records are offshoots of the root level domain DNS so the best fit is whoever is hosting the regular A and PTR records.
example:
emailserver.mydomain.com is your email server and people send emails to
you@mydomain.com, so whoever is hosting mydomain.com needs to add an MX record to point to emailserver.mydomain.com - but emailserver.mydomain.com could technically be a totally different hosting service and IP subnet - like a hosted MS Exchange service.
Of course, if your web presence is under mydomain.com but your email domain is @myemail.com then whoever is hosting THAT DNS needs an MX record that points to emailserver.mydomain.com - but then I have to question why you have myemail.com in the first place, just get an MX record with mydomain.com.
I can understand the confusion and slight "run around" you've been getting.
Clear as mud?