Für alle die es interessiert:

Die Umgehungslösung funktionierte nun längerfristig doch nicht. Sie hat das Hauptproblem nur verzögert.
M.a.W, der Programmhänger trat erheblich später trotzdem auf.

Nach ein wenig googeln bin ich dann auch endlich auf die Ursache gekommen:
An ADO-based application may stop responding when it uses the adAsyncExecute option to open a Recordset object in Windows Server 2003 or in Windows XP

Genau dieses ist das was ich mache.
Mit tausenden von Queries, die ich asynchron machte, hat ADO eben ein Ressourcenproblem und landet letztendlich im Deadlock.

Die Installation des Hotfixes brachte leider keine Verbesserung sondern sogar zusätzliche Probleme:
Näheres siehe hier:
Breaking change in MDAC ADODB COM components in Windows 7 Service Pack 1 (repost with MSDN liveID)

D.h., das Hotfix installiert die 32-Bit-Komponenten des Windows-7 SP1!

Ich könnte also meine Anwendung nur auf Systemen installieren, die ebenso dieses Hotfix installiert haben.

Schöne Sche...!

Ich habe nun das Hotfix wieder deinstalliert und alle Asynchron-Aufrufe in Synchron-Aufrufe geändert, ist zwar unschön, da die Anwendung z.T. eben nicht mehr reagiert (im Fenstertitel mit Hinweis), was einen User zum Abbruch der Anwendung verleiten könnte.
Aber das kann man ja erklären, ausserdem ist es normalerweise eine Batchanwendung.