I have a Compaq Presario 1245 Notebook with a Lucent 'winmodem' which works great under linux. This is of course because Lucent (bless their corporate soul) have taken a bold (?) move and released linmodem to support their modems in linux. Great job Lucent. I dont have the url anymore but I'll mail you the (tiny) file if you need it.
I may be able to get a notebook, and the following are available, Digitec or Asus. Sugestions and hardware compatiable with Linux. I noticed that the Asus comes an HST modem (which may be an "winmodem"), which Linux doesn't work with....