In my personal experience, it was certainly a problem for a while when lists like SORBS and their notoriously hostile de-listing procedures were all over the place. Listed an entire IP block assigned to a data center I had hardware in as "residential" and it took weeks to get it addressed.

And more recently, I'm still unable to send email to Verizon.net email addresses from a VPS because they too insist it's in a residential IP block. (it's not.)

For the first few weeks I had a VPS and moved a small business to it, sending anything to Gmail was a hassle as it was all automatically going to the spam folder. The typical responses from others was "find a new provider" even though checking blacklists showed the one I chose was just fine.

I too have run mail servers, and have seen enough to realize that it's definitely not a myth. It's just that there are enough spammers making a mess of things for the rest of us, which is unfortunate.