Search for "$" on this page: http://paranoia.dubfire.net/2009/12/8-million-reasons-for-re... It is very common for third party service providers to search records themselves on behalf of law enforcement, and law enforcement has historically trusted that and even compensated them.
It's the only way that really makes sense IMO. Can the FBI really bust down, say, Verizon's doors, seize all their hard drives, and correctly generate evidence based on systems that aren't theirs, and may in fact be unique among the phone systems of the entire world? Maybe an email system is simpler, but still.
Also, I think it's inappropriate to seize 400,000 users' data just to (ostensibly) get to one person. But I'm not a lawyer, maybe it is arguably legal.
P.S. Also see https://www.eff.org/files/filenode/social_network/Yahoo_SN_L... for all the things Yahoo does on behalf of LE.