Let's say that company X is PCI certified and compliant as a merchant. In terms of PCI compliance, what does company X have to consider while working with third parties? E.g. for business reasons company X needs to forward hashed PAN numbers to a third-party provider. What does company X have to do in order not to violate PCI compliance?
Although Conor is correct in his assessment of the entropy of payment cards and hashing, PCI DSS is very clear, that a hashed PAN in an environment where the PAN does not exist (e.g. the third party you have sent it to) is not considered cardholder data and does not require PCI DSS's protection. This is detailed in the PCI SSC FAQ number 1089 and for completeness here's the relevant quote:
If the hashing result is transferred and stored within a separate environment, the hashed data in that separate environment would no longer be considered cardholder data and the system(s) storing the hashed data would be out of scope of PCI DSS.
The URL for the FAQ is https://pcissc.secure.force.com/faq/articles/Frequently_Asked_Question/Are-hashed-Primary-Account-Numbers-PAN-considered-cardholder-data-that-must-be-protected-in-accordance-with-PCI-DSS
Typically the third party will provide you with a salt to use, and if they don't then I’d think carefully about their security competence....
In general I'm very dubious about passing along hashed PAN data to a 3rd party, unless they themselves are fully PCI compliant and certified. The issue is that credit card numbers have very low entropy and are relatively easy targets for bruteforce attacks against a hash.
For context, a naive calculation shows that a 16 digit credit card number has 1e16 bits of entropy. However, there is a check digit at the end, and the first 4 digits are typically related to the issuing bank (plus the first digit depends only on the brand, aka Visa, Master Card, etc). As a result there are at most about 1e11 bits, and probably much less than that (the last 2 or 3 times I had a card replaced, only the last 4 digits change). Even without the loss of entropy, a hashing rig like this could generate the MD5 hash of every possible 16 digit credit card number in less than a day. As a result, depending on what hashing method you use, sending a hash over may be no different than just sending the full PAN.
As discussed in comments, you're working with a fraud mitigation provider. As a result they should obviously be very well versed in PCI compliance related to these issues, and should have someone responsible for compliance that you should be able to ask about this. That's your best bet. Again, presuming that they are fully PCI compliant and certified, sending the full PAN data along to aid with fraud detection would actually be reasonable, and that is why sending a hash worries me a bit. Hashing the PAN does add a layer of protection and therefore isn't crazy, but it is also the sort of thing that someone who is not well versed in credit card security might suggest as a way of avoiding PCI compliance issues. As a result, I personally would want to talk to their compliance team and confirm that they are certified and know what they are doing.
I'm not an expert in this area so I can't give you a firm answer, but personally I suspect that behavior analytics combined with email, IP address, etc... are the most effective way of detecting fraudulent orders. As a result if your provider isn't looking at behavioral analytics, I'd chalk that up as another reason to be dubious.