Hi,
I've had nearly the same problem and found the solution. My vServer (from a german provider) has multiple IP-adresses, but just one "main" IP-adress (e.g. 215.234.34.56). Perhaps take a look at your provider profile.
I've to modify /etc/postfix/main.cf:
# For Reverse-PTR for all domains on...