If I were them, they should just get users to use real names and addresses to send e-mail, faxes, and paper mail to the offices of the public utilities commission and to other officials who will pressure them.

Fundamentally, these guys just need to increase social capital with regulators and invest in legal infrastructure. The government is just like another giant company with dependencies and old architecture. Trust me, it's just like investing in weird ERP integration to get access to all of those clients. It's not something that is necessary to the evolution of your product, but it's something you just have to do because the market is just shaped that way.

Also, any press is good press, and once these three get large enough, it'll be widely unpopular to not support them.