Well, now we know what kind of beast we're dealing with!!
The A4 belt system has had a couple of component upgrades in the years following your model. Fortunately, they're all backwards compatible, so if you wind up ordering a (deluxe!!!) kit of parts from
www.dieselgeek.com you will bring your timing belt system to one with a rated life of 100,000 miles!! There are other places to shop, of course, but be careful about which model year parts you do get!! Many dealerships/garages will only put on "original" parts - which in your case brings you back to 40,000 mile (auto) or 60,000 mile ratings...
All the best,
Yuri.