In order to do a search you need to have full GPRS access set up. WAP access is not enough, it must be full GPRS. Many providers only give full access to customers on a monthly contract, Pay as you go customers only get a WAP gateway.
www.mywayfinder.com has a link which allows you to choose your phone type and service provider and it will then send the GPRS settings to your phone via SMS.
You dont need GPS to search or to create a route. The advantage of GPS is that it assumes your start point is your current GPS position so you only have to input a destination, and of course, the real-time instructions as you travel. However you can use Wayfinder without a GPS to plan a route and follow it via itinery mode or map mode, just not in real time.
Using multiple bluetooth accessories at the same time is a feature of the phone. My P800 allows it but I know many other phones can only handle one bluetooth device at a time. In that case, if you're using GPS you have to use a corded handsfree.