Down to 0 bars!
I've been using Windows Mobile Live Search on my WM5 cellphone (no WM6 yet for me :() paired with a Pharos GPS Navigator. Everything works great...except that even a moderate trip of 1/2 hour in unfamiliar territory will drain the battery on the phone something fierce.
GPS functionality was something that I stumbled on in the Live Search when I was waiting around for a delayed flight (what a shock?!). Apparently it got added kinda late and wasn't really publicized. It works great...my only complaint is not enough advanced notice of upcoming turns like a real GPS navigation unit (I also have CoPilot for my PocketPC).
Give it a try...but make sure you have your cell phone charger...