Não, não é necessário que um registro MX
comece com mail.
. De acordo com suas configurações
dig mx example.com
deve dar
example.com. some_ttl IN MX some_priority example.com.
e
dig example.com
deve dar
example.com. some_ttl IN A 216.x.x.x
para que emails do mundo exterior cheguem até você. Espero que ajude.