I'm referring to "remembered" password that the domain keeps so a user cannot reuse that password until it has expired in what was set at Password Policy on DC (W2003/W2008).
Where is password history stored?
The historical password hashes are stored in the SAM along with your current one, so are certainly equally breakable.
I used to run password strength audits for large financials, and part of the output would be analysis of the number of individuals who reused passwords with just a change to the final digit (guess how large a percentage does it!) PWDump and John the Ripper zapped through them quite happily:-) In fact you could get some benefits from the password history that could help you break ones the brute forcer wouldn't get to easily.
To flush these historical hashes, you could try to set history to 0 in security settings and enforce a password change. That might do it, but I don't honestly know. In any case this totally defeats your password history policy if you're hoping to maintain one.