Depends what the situation was before. If the provider previously had other records in place, then it could take a while as many servers will be caching the old records. Those caches can be there for a while, as these days quite a few larger providers ignore TTL values
If there was no reverse DNS in place before it should be a lot quicker - negative caches are normally pretty short.
There's no definitive time to propogate - it depends how the server the user queries is set up.
Reverse DNS services require your ISP to delegate reverse DNS lookups to our DNS servers. Since your IP address is dynamic and comes out of a pool, they will not delegate that control to our servers. If you have a static IP range they should not have a problem delegating their reverse DNS.