They must take down the links from search unless they get a counter-notification. Have they? Ask a lawyer, but I am pretty sure that if they just ignore a DMCA notice you can sue Google for infringement.
It is also possible, that with the massive volumes of DMCA notices they are now getting, they are giving priority to people who look likely to sue if ignored. Sue them just once and they may take you more seriously - and, as far as I know, if you have registered your copyrights in the US, then they have to pay your costs if you win.
As far as policing it goes, you could do what Viacom and Warner do, which is to use a service that sends out automated DMCA notices. Likely to be expensive, but an obvious time saver if there are thousands of infringing pages.