I was using a Swannsmart external 56k modem (an Australian model/manufacturer) until last week when I got ADSL installed
My old 56k modem must have lasted me at least 5 years though.
I used to have an internal US robotics modem when I lived in the States. It was a hardware modem (it retailed for $US80, which is how you can tell), and it worked sweet (ie, kernel driver support.)
Any external modem with a serial connection should work fine with Linux. It's only some external USB and most internal modems that don't work. Make sure you have a "hardware" modem and you'll be fine. (I assume that's why you ask)
Cheers,
Tim