Domænet eksistere i forvejen (på anden server) MXhotel

Du må lige prøve at beskrive processen trin for trin.
Som jeg forstår dig, har du gjort det på denne måde:

Oprettet en MX-record på dit domain på GratisDNS, der peger på mail01.mxhotel.dk med prioritet 10.
Gået på MXhotel for at oprette selve mailserveren med dit domain-navn.

Det vil så sige, at deres mail-setup tjekker om der allerede eksisterer en MX-record for det domain, du forsøger at oprette? Hvis det er tilfældet, kunne du jo forsøge at gå den anden vej rundt og slette din MX-record, forsøge at oprette mailserveren og se om den så også vil oprette MX'en for dig?