I think if I was Google I would do one simple thing. Reduce the voting power of ANY page that accepts paid links to NOTHING. That means a link from Yahoo! directory pages (paid inclusion), BestofTheWeb (paid inclusion), etc. should all have zero influence on Google search results.
I don't think they can completely discount Yahoo. Some of those links aren't paid, they are actual editor picks (like mine =D)
IMHO, Google will never be able to crack down 100% on paid links.You can't discredit a site that charges for a service. Those directories have human reviews, and bring in legitimate traffic because they are popular. Why nullify their value? If anything they are more relevant then most sites that don't charge at all.