Yes they comply with DMCA complaints on the surface. No that's not enough to run this kind of business above the board. What you see in file sharing forums are the same people uploading large amounts of pirated media to these sites, DMCA complaints trickle in over the next few days/weeks, and then the very same people "re-up" the files to the same sites and post the new links in the same thread. Over and over.

To be protected by the safe harbor laws in most nations you need to not have actual knowledge of infringement. If files in someone's account are being flagged on a regular basis, you have a hard time arguing you don't know what they're doing anymore. The indictment against Megaupload says that there's physical evidence of exactly this occurring -- the site owners know that much of their traffic is from users uploading pirated content, even looking into their file lists, yet they reward these users instead of blocking them.