In our application we use the card type and last 4 digits provided by a merchant terminal as a unique identifier for customers. For example VISA-1234.
Since the card number is not actually random (based on the lunh algorithm) do we really get 10,000 combinations for the last 4 digits or is it a smaller subset? If so, is it possible to calculate or even estimate this number?
There are potentially 10,000 combinations of the last four digits. The fact that the last digit is a Luhn check digit does not alter this fact.
As an example, these 10 card numbers have valid luhn digits from 0 through 9. This list has been generated by modifying the 7th digit of the card number in each:
4242420242424240
4242429242424241
4242424242424242
4242428242424243
4242423242424244
4242427242424245
4242422242424246
4242426242424247
4242421242424248
4242425242424249
As an aside, PCI-DSS only allows plain text storage of (at most) the first six and last four digits.