My understanding is that if the phone is linked with a self-hosted Enterprise Server (BES, not hosted by RIM) then RIM don't actually have the keys to hand over.

I would have assumed that a government would have enough cash (and sense) to purchase and run its own BES software, keeping the keys out of RIMs hands.