Any phone with BT can be connected to the Nokia over BT.
Just remebebr many Windows Mobile phones do no support DUN, so you will have to go the PAN way when connecting over BT.

PAN is not offically supported on Nokia N800/N810.
There is a very detailed thread about setting up PAN support using BT-PAN for the Nokia to connect to MS phones.