Has anyone tried to contact these sites to let them know about nofollow? Perhaps they are just ignorant of the technology, since it's not their core competency.
"nofollow is a bad idea and I wish Google stopped using, Matt."
Note that rel=nofollow is just a mechanism to indicate to search engines "Please don't give this link weight in computing reputation or search results." If you're talking about a website that is doing shady things, that's a perfect time to use the rel=nofollow attribute if you link to that website.