Question: where are mx records stored?
Answer: DNS record information such as MX records are stored on Name Servers. It is therefore important that your domain has proper Name Servers so that the Domain Name System can answer queries about the necessary domain name records.