Doesn't
Hayes compatible mean 'conforms to AT command set', in which case, most modems will. As for the 'works with Linux'...any
hardware modem will work, with varying degrees of ease (should be as simple as pointing to /dev/ttyS4 or something), but most PCI modems are software.
Some software modems are Linux compatible, generally those with Lucent chips (take a peek at
linmodems), but they're not normally very easy to set up at all.
HTH