I've successfully paired an Apple Bluetooth keyboard with the E71. Haven't really used it much apart from the fun factor of driving a small cellphone with a full size keyboard. I would guess that pretty much anything should work.
Thank for your helpful post. Could you tell me the model number of the bluetooth Palm keyboard that you have working with your Nokia E71