tl;dr:
It is not possible to do such a thing in a truly secure manner, but it can be done in a "probably good enough" way for being usable and acceptable.
Your options are basically some form of encrypted storage (with the risk of encryption keys being stolen, as they need to be present for decryption), or something involving hashing, with the well-known issues of hashing passwords (a credit card number is basically a "password").
I would implement this as as two-level system where the first level, would be a simple CRC32 and the second level would be a many times iterated secure hash function. Yes, CRC32 is not a cryptographically secure hash, but that doesn't matter in this particular case, since the CRC is not the weak link.
If the thought of using a not-cryptographically-secure algorithm scares you too much, you can still replace the CRC with a cryptographically secore algorithm and only use e.g. the least significant 32 (or 16, for a bigger margin) bits from the resulting hash.
The reason for this approach is that the range of possible inputs only spans around 39 bits[1]. It is practically impossible to hash this keyspace in a truly secure way while keeping the system operational for the designated use.
A brute-force attack on a 39 bit keyspace is not only theoretically feasible, but in fact quite trivial -- unless each single operation is extremely expensive.
The main threat you need to defend against is theft of your database followed by brute-forcing your hashes to retrieve valid card numbers. The next best thing an attacker could do would be querying online whether some unknown number that hashes identically to a randomly submitted number has been used before, or querying whether an already known valid number has been used (neither one is very useful, though!).
Credit cards are usually valid for 5 years, thus for the system to be secure, it must withstand at least 5 years of brute-force. In other words, the work performed for a single verification must be so computionally complex that a dedicated multi-GPU cracking machine cannot perform more than 2^39/(5*365*86400) = 3486.5 verifications per second.
Taking the well-known 348-billion-per-second figure from 2012, the only really secure approach would thus have to store the value of having hashed at least 100 million times. Taking Moore's Law into account, that'd be 200 million by now, and we're not even considering the possibility that someone owns 2 or 3 such machines (or maybe 10).
However, this still does not take into account the fact that banks are inherently stupid and will simply increment the second last digit for a new valid number (and update the check digit). All my credit cards issued during the last 20 years have had the same number with the exception of the second-last digit incrementing 0, 1, 2, 3, ...
Which means that planning for 5 years still isn't enough. Someone knowning an expired credit card number can trivially derive the valid number of the follower card. You therefore need to plan rather for something like 30 years, not 5 years. I'll leave extrapolating Moore's Law to another 20-30 years for homework.
In conclusion, for the system to be really, really secure, your server would have to perform the equivalent of a trillion hashes (or more) per verification, which at a rate of, say 10 million per second for a typical CPU implementation, would take over a day. In other words, the system is completely unusable for its designated purpose.
Something that's several orders of magnitude faster is needed. Most queries will be negative queries, and a simple, fast hash could be used to prune out 99.9% of all negatives, if only it doesn't render the already weak security even weaker. This is where CRC32 comes in.
If the CRC32s of two credit card numbers don't match, it is guaranteed that the numbers are not the same. Most of the time, that will be the case, and you can immediately return "No!". You can skip 99.9% of the work without giving anything away.
If the CRCs do match, it might be a hit, but there is a chance of a hash collision. Now, the secure cryptographic hash (which would have at least 160, better 256 bits) is calculated and compared. The likelihood of a collision is neglegible now. If the hash matches, it is certain that the number matches.
CRC32 contains 32 bits of information. It is impossible to restore 39 bits of information from 32 bits, no matter what computional resources you may own. Therefore, the CRC is safe to use in this case (or at least, it is not less safe than anything else).
As pointed out by Ben Voigt, it is of course still possible to guess the information that cannot be restored, and 7 bits to guess aren't a terrible lot (concatenating the expiry date will make this 15 bits). That is true, but there is not much you can do about it.
What about CRC and security anyway? CRC is not cryptographically secure. It is relatively easy to tamper with bits to get a desired output (not a problem here, would be with logins), and the function can be trivially reversed (4 table lookups, plus a few shifts and xor) to a 32 bit input, a somewhat bigger problem. Luckily, but this bit pattern is pretty worthless since it isn't a valid number, nor a subset of any 39-bit pattern that might be a valid number (other than by sheer coincidence).
Brute-forcing the complete 39-bit keyspace is more straightforward than trying to play tricks on the CRC, since, unluckily, this is easy enough and fast: A SSE4.2 implementation uses about half a cycle per byte (so, 2 cycles per hash), which means a desktop computer could do the complete keyspace in a second or two (assuming the keys to compare with all fit in L1).
The exhaustive search would reveal all 39-bit patterns that have the same CRC, which means they could possibly be credit card numbers, and using Luhn's algorithm the attacker can immediately discard 9 out of 10 numbers which cannot be valid. That's bad, admittedly, but it is really just a consequence of not having too many input choices and having a check digit implanted on top!
Still, the CRC is actually stronger in this scenario than a cryptographically secure algorithm: Given 2-3 billion credit cards in circulation worldwide, the chance of a collision using a 160-bit hash is somewhere around 1 to 1020, and don't even think about the chances using a 256-bit hash. Which means that any hit during your exhaustive search of the 39-bit keyspace will immediately give you the one and only guaranteed valid card number. A hit on the CRC32 will only give you one of many possible numbers.
One thing you could do to trade some speed for security would be to further throw away some information from the CRC, for example, you could just discard the most significant 8 or 16 bits of the CRC, which would add these to the bits that an attacker will have to guess. Of course this will somewhat reduce the effectiveness of the pruning, but not too drastically. Instead of pruning 99.99% of the work, you might end up pruning 99% or 98%, which is still mighty fine.
The second level of verification, as stated above, needs to be a cryptographically secure hash that runs at least a million iterations much like it is done in a key stretching scheme (actually it needs much more than that, but the system needs to remain practically usable, too).
The implementor needs to trade risk versus usability here, a server should at least still be able to process a few dozen requests per second. Customers/merchants will not consent if looking up one number takes several minutes (or longer), no matter what the security implications are. Nor is it practical to have more or less one dedicated server dedicated per merchant.
Since matching is only interesting on a per-merchant base, one could use a constant-per-merchant salt and store card numbers redundantly along with an index on the merchant's ID, which should be within the powers of any reasonable database system.
[1] A credit card number has 16 digits of which the last is a checksum derived from the others (Luhn algorithm). The second but last digit is usually (not necessarily, but usually) the sequential card number, starting at zero for the account owner's first card, 1 for the spouse or a replacement card, 2 for the next card thereafter, and so on.
Further, the first three digits encode the card issuer and the bank, and only use about half of the possible number of 3-digit combinations.
All in all, this leaves us with betwen 12 and 13 complete decimal digits of entropy, which is anywhere between slightly over 36 bits, and 39 bits.
I would recommend concatenating the expiry date to the number, as this will make this situation a bit less miserable. My credit cards are always valid for 5 years (not sure if that is the universal rule, but I'd assume so), so adding the expiry date would add 5*12 possibilities, or 5.9 bits (these come pretty much for free, since you need the expiry data in a transaction anyway!).
