I have an N810 and am having essentially the same problem you had. Any attempt to pair the N810 with M500 results in it locking up. Using the refrigerator procedure you describe, I can actually get them to pair (crazy!). However, if I use this procedure, the N810 doesn't seem to recognize the M500 as a phone. It does not prompt me to set up and internet connection, and "Sprint" no longer appears in the Connection Manager. Did you have a similar problem? How did you get around it?

Update: After trying like 10 more times, I apparently timed it just right such that both ends got enough information to pair successfully, but not so much that the M500 locked up.

Before that, though, I found the misconfigured bit in the N810. gconftool -R /system/bluetooth/ADDRESS/services had a bare list. When the N810 paired properly, the list was:

services = [telephony,object transfer,capturing,networking,DUN,OPP,00001112-0000-1000-8000-00805f9b34fb,HFP-AG,FTP,0000110a-0000-1000-8000-00805f9b34fb,0000110c-0000-1000-8000-00805f9b34fb]

Probably DUN is the only one that matters in that list. Some other relevant keys are:

dun_gsm = false
dun_umts = false
dun_cdma = true

So, with some gconftool magic, I bet I could have overridden the faulty keys on the N810 to get working internet without wearing out the door on my fridge