When I had my Nokia E62, I was happy with the Holux GPSlim 240 SiRF III Bluetooth GPS Receiver, it's the size of a pack of Wrigley's gum. Uses the same mini-USB connector to charge as the BB too, eliminating the need to carry another charger around.

That said, I haven't tried to pair it with the 8800 (since well, it has the built-in gps and all), so I can't comment on performance paired with a BB.