Storing only a secure/irreversable hash of the password should be standard practice these days. I'd say that anyone who stores plaintext passwords is running serious liability risk. So I expect that what the gummint actually asked for was the hashed passwords and the formula for the trap door hash the company is using.
Given that, they can afford to throw computation at it to do an exhaustive search for the password. "Infeasable" carries the caveat "within a reasonable budget, and assuming you're looking for a specific password rather than bulk-matching against the entire file" -- and government and reasonable budget are known to not always occur in the same sentence. (Not to mention that the definition of "reasonable" depends on how important it is to you to get the answer.)
Note too that when you've got a hash, they don't have to find the right password -- just one that has the same hash value.Unless the hash has extremely low odds of collision (eg has many more bits than the passwords do and scatters well across that space), that does represent a slight weakening of cryptographic strength in exchange for the huge gain of not having the passwords ever stored as plaintext.
Remember recently published studies (some cited here on BB) showing that even an unsophisticated effort can brute-force a huge percentage of a typical pile of passwords. Sure, a trapdoor cypher which is more expensive to compute does reduce the speed of that result... but that's typically not going to be by much more than an order of magnitude or two, for a given size password.
We need to train people to use longer and less obvious passwords. At least on systems they care about and that might offer progressive attack paths against other systems. That's got better odds of better protection than just running fancier math on a short single-word-or-common-phrase password.
Either that, or people need to learn that anything on line should be presumed to be insecure.