There is no need for a PTR for the dedicated IP because mail is sent from the hostname, which resolves to the main server IP, so the problem is likely something else.

What sort of bounce messages does he get?