It's not beyond the realm of possibility. We usually have one of our clients impacted by this at least a couple of times a year, although those are all in shared hosting environments IIRC.
However, some RBLs are extra aggressive, and some ISPs use things like Barracuda spam firewalls which love to take advantage of the most aggressive RBLs. If you host with a network that's got a reputation for hosting spammers, you could find that your dedicated IP is included in a /24 on one of the RBLs.
Or, if your IP resolves to a hostname associated with the VPS provider, that might get you flagged for spam.
It's impossible to say for sure without knowing exactly which provider you're looking at.
I've been hosting a mail server on Linode for a couple of years now with not a single instance of ending up on an RBL. A handful of my clients are hosting with me now as well, including one who sends out a monthly newsletter to around 500 subscribers (customers who have given him their email address specifically to receive the newsletter). Linode's got a pretty good reputation and when one of their other nodes attempted some ssh abuse against one of mine, they responded quickly.
So don't host with sleazeballs and you should be fine.