In order to build a secure challenge-response system where the challenge is forgotten by the server before the response is returned, you have to make sure that an attacker can't send you a response to a challenge you didn't send, or a challenge that was directed toward someone else, or a challenge that is old or has already been used.
First of all, you can make sure that all of your challenges are genuine by "signing" them in some way. You don't have to use traditional signing protocols to do this since it's not a general-purpose signature. Instead, just take your existing challenge, append some "secret" string to it, and take a cryptographic hash of the result (e.g. SHA-256). Then include the hash as part of the challenge. When a you get a challenge back from the client, you can verify its authenticity by repeating the process, and comparing the transmitted hash with the one you compute. If space is a premium, you only need to include a small subset of the entire hash.
To make sure that challenges can't be used to authentiate against someone else's account, you can make the account identification part of either the challenge itself, or part of the authentication described above. That is, instead of just appending a "secret" string, you can append both the username AND a secret string, and then hash THAT. Similarly, you can tie challenges to a given connection ID, IP host address, etc., by incorporating that information into the signature.
Finally, you can make challenges time-sensitive by incorporating the current time into the challenge content, and you can prevent replay attacks by giving each challenge an ID and disallowing responses that refer to an already-used ID.
Your system can look like this, as an example. Note that this example is just off the top of my head, while yours should probably be a bit more sophisticated than this. But this at least demonstrates how such a system could work.
say: My name is "Alice"
* super-secret key is "swordfish"
say: Please sign this string: "Alice|30Nov11@12:03|4f9167de1e"
* password is "mustang"
* say: Challenge was "Alice|30Nov11@12:03|4f9167de1e"
* say: Response is "6148f8d7bd9eeb6c9156c5be385e96871721f6df"
* verify that user's name is in the challenge
* verify that timestamp is no more than 5 minutes in the past
* verify that "4f916..." corresponds to challenge with checksum replaced by "swordfish"
* verify that response is challenge with user's password appended