[rudra]

if you are using ns servers provided by your domain registrar, then you should add mx records there (along with other records like spf).
in case you have delegated dns record keeping to some other name servers by adding ns records at your domain registrar, then you add mx record at the dashboard (or command line.. nano.. whatever) of that nameserver provider.

I know my reply is really short.. sorry.. I dunno what else I could add.

let me try once more.... ahem

you add all such records to your name servers. so wherever your name servers (NS) are managed, you head there.

example. Let us talk about eu dot org domains.

say i got MyDomainExtension dot eu dot org

now I can either add only NS records for this domain and then I could say use name servers from dns dot afraid dot org (free) or some other dns hosting provider to manage dns records for my domain.

or,

i could add a cname aaaa txt spf records etc for this domain right there so the eu dot org name servers get used for this.
i could also add ns records for subdomains under this MyDomainExtension dot eu dot org and delegate control over the associated records to some other nameservers.

re. HR is the fastest and the best as ever. yea... you need both spf and dkim for properly functioning mail system and delivery.