I don't have a definitive answer for you, but I can share my experience. I got my T3 to pair as well, and had about as much trouble as you had. Palms are funky with regard to BT and WIFI, so I wasn't surprised at all.

Why are you trying to pair them for an Internet connection over BT? The microbrowser is light years ahead of anything that is available for the Palm OS5. Surfing via my T3 over Wifi was never really great fun. However, if you want to surf using your Palm over WIFI, you might be able to find a cheap Palm SD Wifi card. I should warn you, though, that my battery life was just about worthless (45 minutes) for surfing over Wifi.

As for what BT services are recognized, I'm not sure what you can do to change this. The services have to do with what each device presents to the other. Without doing further research, I'm guessing that the N810 does not present the "modem" service to other devices. As such, I doubt it can be set to do so.