A couple of things to consider is that changing the A record is a start. I would suggest also changing the lifetime on the record to a shorter timeframe. This way the record will expire quickly and changes will propagate faster.
I would also recommend putting another MX record in with the weight or priority set lower on the record pointing to your organization’s mailserver. This will ensure that messages are delivered through your server(s) before hitting theirs. By adding another MX record pointing to your Exchange servers, you can shut theirs down from accepting inbound requests on port 25 and all messages will be stored on your server then for the customer.
MX records do not have to match the customer’s domain. For example:
customer.domain.com IN MX 100 server.hosting.domain.com
customer.domain.com IN MX 200 server.customer.domain.com
Where server.x.domain.com is an existing A record.
Since the first record is lower priority, inbound servers will attempt connecting to this host first. If the first server does not respond, then connections are attempted to the second host. If the host is not available, the sender’s system may retry for some set period or send back a non-deliverable notice to the original sender.