In the MX records that are provided with your DNS Zone, there is an MX record that is automatically added, which you need to remove if you are not using an OVH provided email.
For example we use Gmail Business Apps. As you should only have one set of MX records for one provider, if you have ‘redirect.ovh.net.’ in your error message - via Google then you have mixed up your records and need to remove it.
The google MX records are readily available for google email, just google them. Ensure you have copied over the destination and the priority as per the instructions on google setup. They have the details for configuring ovh for google for business email.
The reason i’m writing this is because I realised this was the problem after receiving the bounce back email from a client. I looked up for an answer but didn’t find one, so added it here.
Hope this helps,