I have the GPSlim 236 from Holux and it works great with my Nokia 5500 over bluetooth. I use the mapping software from Nokia. It tells me where I am and can plot routes. The maps can be pulled from the internet and stored on your memory card. You do have to pay if you want to use the navigation feature.
I just checked and my BT GPS works with google maps too but like you said you pay for the GPRS connection to get the maps.