As I understand your situation:
- You have to store, on the server, some data ("messages") which the user must be able to read.
- The server may be able to read the data at some point, if only transiently.
- But the server should not keep this power permanently. If an attacker steals a complete copy of the server hard disk (e.g. a full backup), then he should not be able to read the data.
- The user, being a user, has very little storage capacity on his side; at best, he may remember a password and/or possibly a recovery code which the user wrote down on some paper at his home (but while the user may accept to type his password on a daily basis, he will refuse to enter a huge, fat recovery code that often; the "recovery code" should be a way to recover from a forgotten password).
Under these conditions, the only possible solution is that some password-based encryption is done. Indeed, the combination of the data stored server side and the user password should be enough to recover the data. Since we are talking about the Web, the client is feeble, when it comes to computational tasks; so the encryption and decryption will have to be done on the server. Anyway, you want the decryption to be done on the server, so that any data formatting (turning the message into HTML) occurs on the server as well.
What you describe is not far from the truth (where "the truth" is "the best you can hope for"). Namely, you will have to do the following:
For each user, there is a user-specific symmetric key Ku. That key is generated server-side when the user account is created, with a strong PRNG, and has appropriate length (say 128 bits -- 256 bits are overkill, but hey, go for 256 bits if you need a big number to woo investors).
For each user, a "recovery code" Ru is generated along with Ku, with similar characteristics. This will be used if the user forgets his password. The encryption of Ku, using Ru as key, is stored on the server (let's call it Fu). Ru is sent to the user, with instructions to print it or write it down and store it safely.
Each user has a password Pu. A hash of the password is computed on the server, using a good password hashing function like, indeed, bcrypt. This operation requires a user-specific random salt Su, which is stored on the server. The hash value is extended into some bits (say, 256 bits) with a key derivation function. If you only need 256 bits, then SHA-256 will fit nicely as a KDF.
Note that we want to extend the hash output only; most bcrypt libraries produce an output as a string which encodes the salt and the hash output. You want to recover both values separately, because you want to store the salt, and you want to have the hash output alone for input to the KDF. It may be simpler to replace bcrypt with PBKDF2: PBKDF2 is its own KDF (output size is configurable) and most PBKDF2 implementations already handle salt and output separately.
The KDF output is split into two halves (e.g. two 128-bit values). The first half is Vu, and is the password verification token. The server stores it. The second half is used as a key to encrypt Ku; that encrypted value (let's call it Eu) is stored on the server.
So, for the user U, the server stores Su (the user salt), Fu (the encryption of the user key Ku with the recovery code), Vu (the password verification token) and Eu (the encryption of the user key Ku with the password-derived key). All "messages" for user U will be encrypted with key Ku.
When the user logs in, he sends his name (U) and his password (Pu). Using U as index, the server recovers the stored data. With Pu and Su, the server recomputes the password hash, then extended with the KDF. If the first half of the KDF output is not equal to Vu, then the user's password is wrong, and the user shall be rejected. Otherwise, the user is authenticated (the server has some guarantee that the client is indeed the genuine user U), and the second half of the KDF output can be used to decrypt Eu, yielding the key Ku. At that point, the server knows Ku and can do all the encryption/decryption business.
If the user wants to change his password, then a new salt will be generated, the new password entered, the hash function computed again, yielding a new verification token, and a new Eu. The key Ku, though, is not changed, so the stored messages need not be touched in any way.
If the user forgets his password, then the recovery code can be used as a sort of "alternate password" in order to recover Ku, at which point we are back to the "password change" situation.
Now for some important notes.
When the server learns the user key Ku, then the server should keep it in RAM only. You do not want Ku to hit the disk (that's the whole point of the exercise). Therefore, you shall mind a few thing:
PHP sessions are written to disk. What you put in session variables become files ! But you can choose the destination; e.g. you can use a RAM-based filesystem that will be shown to PHP as files, but is really RAM. Alternatively, there is a shared memory support so that no file at all is created (this may be safer; if an attacker hijacks the live server than he can read all files, including those on tmpfs; but such an attacker could also plunder PHP's RAM directly, and read all session data anyway).
Virtual Memory, aka "swap space", can induce the kernel to write to disk what is usually in RAM. Swap space is not backupped, but that's still writing. An industrious attacker will scan your garbage cans in search for old, discard hard disks. If a disk fails (electronic board fried), then you cannot wipe out its contents (at least, not easily), but the attacker may recover the data (by replacing the board).
It might be a good idea to disable swap altogether. Running without swap is fine as long as you have sufficient RAM; and you really want to have sufficient RAM anyway because hitting swap space really kills performance, especially in GC-based languages like PHP. Virtual Memory is one of these ideas which were very good.
To some extent, what you do not want to put in session variables can be stored as a cookie on the client. Cookies are not really permanent (if the user has several devices, cookies might not be shared between his browsers) but they can benefit from some "secure storage" -- as secure as things can get on the user's computer.
You are talking about messages... so maybe you want to encrypt some data for a user, when this user is not logged in. In that case, the server might not know Ku. To solve this problem, you will need asymmetric encryption: make Ku the private key of a pubic/private key pair, the public key being stored "as is" (unencrypted) in the database. Encryption uses the public key, while decryption requires the private key.
Doing asymmetric encryption properly is kind of complex; it requires the assembly of several cryptographic algorithms, and there is ample room for devastating mistakes that cannot be detected with tests. You are warmly encouraged to rely on an existing format and software; e.g. GnuPG bindings for PHP.
I strongly hope that all communications between client and server use SSL, i.e. HTTPS; and any relevant cookies are marked HttpOnly and Secure.