"A communications card has been inserted" ...
... let the fun begin! The card is a PICO PCMCIA Type II Bluetooth card. Currently, there are large numbers being sold on eBay in Germany, so I invested the donations I've received so far (thanks guys!) and got one for myself.
This means that I can start with the probably insane task of implementing a Bluetooth stack for the Newton. At least the RFCOMM part...
As for the cards that finally might be supported: They have to be PCMCIA Type II cards (16 bit, 5 Volt - 3.3 Volt might work too). CardBus cards such as the newer Belkin models won't work.