Let's do mathematics. I like mathematics.
You generate passwords in a space of size n = 6232 (32 characters chosen randomly, uniformly and independently of each other, in an alphabet of size 62, i.e. all uppercase letters, lowercase letters, and digits). Suppose that you have generated k such passwords; k is easily estimated since you will produce about 2000 potential passwords per week (100 "true passwords" but each of them is chosen among 20 fresh random passwords).
It is easily seen that k will remain much smaller than the square root of n (indeed, k will be in the vicinity of the square root of n only after about 457 thousands of billions of billions of years). We can then approximate the probability that you ever obtain a collision (i.e. the same candidate password shows up twice) to be about k2/2n. Assuming that you keep your system going for a hundred years (which is already preposterous), i.e. about 5218 weeks, this yields the probability of close to 2.4·10-44.
Now compare that with the probability of your security advisor being mauled by a gorilla escaped from a zoo; that probability is at least 10-18 per day (I have made this comparison before, and then again because I love this example; and the actual probability is higher than that, but let's be conservative). Therefore, on average, before hitting a collision, your security advisor will be visited by at least 4.7·1025 murderous gorillas, i.e. 47 millions of billions of billions of gorillas (since that far exceeds the number of living gorillas, one has to assume that some of them will come several times). If the advisor still worries about the collision and not the gorillas, then you have demonstrated that this advisor is no smarter than a baboon.
To sum up, it is easy to ensure that no password is reused: the Universe already makes it so. By doing nothing special you are already ensuring this absence of collision, with a success rate which is billions (of billions) of times better than your success at protecting your security advisor (and his children) from gorilla attacks (and you are probably already doing a good job at that, too).
Now let's suppose that your security advisor is unmoved by mathematics, because he believes in pretty pictures more than in pretty figures (in that respect, he would be no different from the average chimpanzee, so at least there is some kind of ironic consistency here). Setting up a system to filter out "duplicates" would be a waste of money, and, crucially, a way which can be easily demonstrated (e.g. to the boss of that "security advisor") to be a waste of money (be sure to make him aware of that fact); however, he may still insist on it, because he suggested it first and reneging on his own past word would endanger his perceived alpha-male status (again, chimpanzees come to mind). This unfortunately happens a lot with humans. Then your job, after having duly warned your hierarchy of the complete inanity of it (leave written traces ! They will protect you when somebody with more than three brain cells does an audit), is to make sure that, at least, this duplicate-detection system does not weaken the system. The duplicate detection is wasteful; let it not be harmful.
The space of possible passwords is very large, a bit more than 2190. All passwords are equiprobable, so you have about 190 bits of entropy, which is huge. For such passwords you DON'T NEED good password hashing because all of the features of password hashing functions (salts, iterations...) are ways to cope with the inherent weakness of "normal" passwords, i.e. the fact that they have low entropy, and thus can be brute forced (this is called a dictionary attack). However, your passwords have way too much entropy for brute force to be even remotely applicable to them (even if you somehow hire the gorillas to try passwords, you will run out of gorillas much before you run out of possible passwords). Therefore, simple hashing would work: store the hash values in a database, which will allow you to do a fast "already used" check.
However, there are systems out there who "use passwords" by actually hashing them and using the hash value as "the passwords". Windows in particular: when it uses a password, it actually works over the MD4 hash value (128 bits) computed over the password. Therefore, if you store hashed passwords and happen to use the same hash function as some other password-consuming system, then you are actually storing "cleartext" passwords, and that's bad.
To avoid this problem, use "your own" hash function, which in practice means HMAC. The hashing process would look like this (in C#/.NET):
static byte hmacKey = Encoding.UTF8.GetBytes("my security advisor is a chimpanzee");
static byte HashPassword(string password)
HMAC h = HMAC.Create();
h.Key = hmacKey;
It is quite improbable that any other system out there uses the same password hashing function (i.e. HMAC with the same key), so storing these "hash" values in a database would be safe, and allow duplicate detection.
Now the killer argument: why, oh why, would you want to detect duplicates ? A system which detect duplicates is also, inherently, a system which can tell what passwords are (or have been) in use. Such a system can only harm security: it helps attacker know whether a given password is "worth trying" on a system. Fortunately, the sheer size of the space of possible passwords in your case voids that harm. However, in all generality, insisting on detecting duplicates is also insisting on weakening the protection offered by the passwords. This is bad, bordering on malicious.
It would be relatively easy to suggest, with some careful wording, that the security advisor is trying to plant a backdoor (of course, not a very good backdoor, because he is not good at it, but intent is what matters in criminal cases). For instance, consider the following setup: you design a system which helps users generate 4-digit PIN codes for their bank smart card. The smart card will block itself after three wrong PIN codes, so an attacker who steals the card has only probability 1/3333 to guess it. However, if there is a system which generates random PIN codes and avoids duplicates then the attacker could hijack that system (e.g. dump its database with some SQL injection attack) and then let it generate 9999 PIN codes, which will all, by construction, be different from the PIN code that the smart card user obtained. This reveals the user's PIN: it is the only one, among the 10000 possible PIN codes, that the anti-duplicate system will not generate.
That's the core of it: when preventing duplicates for passwords has any detectable effect (not your case here, because duplicates won't happen in your lifetime or even in the Sun's lifetime, for that matter), then that effect is negative. This is a BAD IDEA. It smells of foul play.