1. I would always be wary of no name receivers but others seem to have used them with success. Holux & Globalsat are two of the more respected brands.
2. I have no experience of the Palm but BT connectivity on Windows based PDAs seems solid enough.
3. Tom Tom are a rather poor company from a support perpective (IMO) but their software is probably as good as it gets. I fon't think the latest Navigator 6 software is available for Palm yet so you would have to track down V5.
4. The software isn't very big, it's the maps that require space. Tom Tom's latest GB map is 240Mb although that also includes major roads of western europe.
You will also require some form of PDA holder for the car. This will need to power the Palm & maybe provide amplification for spoken instructions, depending on how loud the Palm goes.
You can find a whole lot more info on a dedicated Palm/GPS forum
here.
I would have to say though that given the continuing falling prices of all-in-one units, buying into PDA based SatNav is becoming pointless. The Tom Tom One (GB) can be bought for around the same cost of buying software, GPS receiver & PDA holder for the Palm.