I'm sorry this is gonna be a very very long reply, but I've been using Mobile XT from ver. 4.20.20, and I need to explain my experiences with you.
I know. The recalculating using the phone's GPS module can be very frustrating. I will try and help you the best I can.
I've found that upgrading Mobile XT every time to a newer version causes problems. So I decided just to uninstall the previous version including the Garmin maps, and start from scratch with every new version. I found this when upgrading from 5.00.20 to 5.00.30 that 90% of the routes would take me on very nice 300km+ scenic routes where as the route was suppose to be only 15km.
Things you can try in Garmin XT in your case
-> Tools -> Settings -> Map -> Show Location; When choosing "On Roads", it will drop you on the nearest road closest to the GPS location. This means that different road running next to the one you're driving will be picked up by the gps which will cause recalculation.
-> Tools -> Settings -> Map -> Map Detail; Lower it and see if that makes a difference. I've noticed the more detail I have the more recalculations I have
-> Tools -> Settings -> Routing -> Off-Route Recalculation; Don't set it silent. Either "Prompted" or "Automatic - Announced". That way you can figure out if the recalculation was due to inaccurate gps location.
I'm using N95 8GB running Garmin Mobile XT 5.00.40 with a-gps turned on. A-gps does use data. And where gps signal are bad, a-gps works overtime, because it will try and find as much cell-network antenna as it can store. And then we don't even want to think about roaming with them.
I've tried those tutorials on the net to solder a piece of wire to the phone's existing gps antenna, but really not worth it. The resistance of the existing antenna must be matched, otherwise you'll have to have a piece of wire hanging out the phone. We have done extensive probing on three n95's and four n95 8gb's to boost the gps signal to the point that the phone later decided to light up a cigarette and said enough is enough.
Your best bet is to get an external bluetooth receiver, if you don't plan on using a-gps. It really is a good investment to get one, as it is very accurate and get signal very fast. I have purchased a receiver that is so small, it's actually called a keyring gps receiver.
IMHO, buying a receiver is a once-off buy; using a-gps, you'll allways have the thought of how much it costs in the back of your mind, which in it's turn contradicts concentrating on the road :D
I can't really confirm anyone connected to a normal garmin gps like the the Nuvi, as the bluetooth feature on the new ones is mainly used to connect to your phone and used as hands free, POI dialling and looking up contacts.
P.S. Have you tried Nokia Maps yet? Upgrade it to the latest and see if it helps. Also, it asks you to go online in the beginning, which is a-gps. I'm using both Garmin and Nokia Maps and IMO, I think the module and antenna in the phone causes inaccurate gps location, not the software. The software will cause inaccurate route planning.