Problem with Reverse DNS

[M. B?ttger]

Hello,

i have a problem with an reverse DNS-entry.
The situation: 
We have an IP-Provider who gives us the lines and the IP's.
Then we have a Domain-Provider who links our domains to the IP's.
afak the Domain-Provider is in charge for the 'normal'/forward DNS
while our IP-Provider is in charge for the reverse DNS.
Is that correct?
Both of them say they are not responsible for that, because the other
side is.

I think the IP-Provider is in charge for the DNS-Entry.
Right?

We need this entry for mailing to aol (and maybe others).
aol blocks all of our mails because of the missing reverse DNS.

Thanks in advance for any hints or tips
Michael Boettger