Did a bit of Googleing.
Apparently there are a few options, most of them online (GPRS traffic).
We-Travel seems to be the only one which can do without network traffic:
Ubinav and Garmin Mobile both use a GPRS connection thus generating network costs. I imagine it can add up when you are roaming...