How should passwords be stored if they must be recoverable?

Don't force yet-another-password on your users. Use PKI, hardware tokens, or some other method like OAuth or OpenID that leverages some Identity Provider site which sits outside of whatever jurisdictions you're worried about.

Note that the actual requirements of the 2004 French law in question Loi pour la confiance dans l'économie numérique aka Act on Confidence in the Digital Economy are not clear and it seems that some reporting has misinterpreted or exaggerated the effects. For example it sounds like it may be sufficient to simply provide law enforcement with some other access to the user's account, e.g. for a child pornography investigation, in a way that doesn't tip the user off that their account is being accessed (as a typical password reset would).

Use Public Key Cryptography. Your server will only have the public key. This will allow the server to encrypt a password and then can compare cypher text in order to authenticate a user.

The private key should be on a drive inside a bank vault. If the french government demands a password, then you can access to the private key to decrypt the password.

This questions has been debated, in one form or another, for some time as the "key escrow" problem. There are fundamental problems with the architecture of giving a third party access to secured data. These are invariant to how you implement the cryptography. See this article for example.

I am interpreting the question as how to provide third party access to secured data: the debate about whether this actually corresponds to the current situation with the French government I'm considering tangential; and there are unsolvable risks with doing this by the nature of the problem. So consider this answer as making the best of a bad situation.

A set of requirements could be:

1. The server has access to all the records
2. The government can be granted access, but only to specific records
3. It should be fairly efficient to register a new user
4. It should be very efficient to authenticate a user
5. It doesn't necessarily have to be that efficient to recover a record

There is actually a very nice solution to this problem with very modern cryptographic techniques, called functional encryption, however it is not efficient. With these types of schemes, the server can hold a master private key that allows them to decrypt any record and they can create a new private key that can only be used to decrypt specific records. This solves (1), (2) and (5), conflicts with (3) and does not provide (4).

In order to provide (4), I'd suggest a hybrid system where whatever existing password-based authentication system is being used is continued to be used to do (4), and it is augmented with an encryption of the user's record (including the password). If the record is provided to the government, once it has recovered the password, it can compare ensure it is the same password being used to authenticate the user.

An alternative to using function encryption would be for the server to encrypt the record with an appropriate encryption scheme that allows them to generate a "zero-knowledge" proof of what the record is each time the government asks for a record (instead of giving the private key). The proof could be encrypted during transit to the government (and one could even use a "designated verifier" proof to stop the government from sharing the proof with others).

None of these solutions will ever solve the fact that the government needs to be trusted not to abuse its authority, since protecting against this conflicts with the definition of the problem we are trying to "solve."