HMAC-SHA256 for hashing of credit card PANs? Assume you had no option (really) but to store thousands of credit card PANs in a file.  You do not need to decrypt them ever, but you do need to use it for checking if a given (new) PAN exists in that list. 

To protect the PANs, the idea is to HMAC-SHA256 them.  This scheme naturally relies on the HMAC secret remaining secret.  Please assume for this question we can take that as given (HSM).   Also, that the secret is a truly random 64 byte secret.  

Is there any kind of attack that could be realistically mounted to crack this?  One can reduce the search space by knowing that credit Card PANs have an obvious pattern - from 15/16 digits,  one can remove the luhn digit, and the first (say) 6 digits (BIN). 

An attacker would pick a likely BIN, and then iterate through the 10^9 possible PANs, hashing them against every possible key. 

This looks to me like it would take longer than the universe's expected life, even with incredible hardware.  Exhaustive hashes required = 10^9 * 2^512.

Having prior knowledge that a given PAN is definitely on the list,and thus dividing the number of hashes by 10^9, does not make any real difference. 

Have I missed anything here, or is this reasoning correct?
Under your assumptions, everything will be secure, as long as HKDF is secure and your key is secure (assuming attacker has only offline access to data, not be able to for example check if given credit card number was already entered). Currently even 2^128 is far out of our reach. But I wouldn't say that this will remain until end of universe. It is possible that in future we will find SHA-2 weaknesses and be able to use them to crack your solution.

Your scheme can however be easily broken if key was stolen. If this is consideration, you can reduce output size and increase risk of collision while making attacker struggle with same thing. However, I have no idea if this allowable in your scheme since you didn't give any details on how such thing would be used.

All in all, I would be most scared of flaw that would give attacker ability to do, what you can do: Check if number is on list, because of breach and access to HSM interface (which can also suppress any warnings of hash rate etc.).