Mail Migration DNS Question

We currently have a large number of clients who we manage mail hosting for. We are about to move to a new mail provider and I have a question about the changes we need to make to DNS to have this happen as efficiently as possible.

Our current clients all have an entry in their zone file as follows (actual domain names have been changed):

ourcustomer.com MX IN 300 mail.ourmailserver.com. [Preference = 10]

mail.ourmailserver.com is a domain name we control and currently it as has an A record for mail.ourmailserver.com which points to the IP address of our current mail server.

My question is - if we migrate our mail to a new provider do we need to update the MX record for all our customers individually or can they stay as they are and have us just make a change on our domain for where mail.ourmailserver.com points to? If so, what would the change be?

The other complication is that many of our customers also have an A record created as follows:
mail.ourmailserver.com. A IN 300 XX.XX.XX.XXX
Where XX.XX.XX.XXX is the IP address of our mail server.

I presume we would have to delete these records?

I am not a DNS expert and would really appreciate some views on this.

Thanks

David