They have some other cool stuff to do than resort to such a manual labor of emailing each and every sites in the world. Yes, what you described is probable but unlikely.
Sounds like a new realty show coming next year! CSI-SEO-WWW They put SEO companies on an island and see who first uses black hat and forms an alliance to get off the island! Of course they can't send a letter it is entrapment. You can buy links but you must use a no follow attribute otherwise then it's not following search engines guidelines. Sounds to me like someone fishing for links to buy without asking for it maybe scared to say so!
Let's be honest. Paid links are created to manipulate search engine algorithm, obviously. If you can sit on the no. 1 spot without any paid links, why you should buy any links, is that only a waste of money? But because many people want to be on the top spot without providing any interesting content, they bought links. Back to the real question, I believe it's very easy for Google to penalize link sellers manually but it will be very time consuming. That's why they prefer to strengthen their algorithm although the process is still quite slow.
What one man calls "paid links" another calls advertising. Websites bought text links before Google was even in existence. Their algo will never be smart enough to be 100% sure "why" a link is on a page. They should concern themselves with other ways of strengthening their algo, not pressuring decent people who are trying to make a living online by selling ads on their websites.