Yes, I already did that.
I also gave Toby's advice a try, packaged Adobe CS 5.5 with their Application Manager and installed it to "C:\ADOBECS55". Unfortuantely, that made no difference.
Regarding the "Missing plugin error" Adobe has these solutions (this applies to CS3, but could possibly work on CS 5.5 I guess):
Solution 1: Re-create the Illustrator preferences files.
Solution 2: Verify that the required font is installed and active. (Tahoma on Windows XP, Segoe-UI on Windows Vista)
Solution 3: Run Illustrator in a new administrator user account.
"A damaged user account or an account with limited system permissions may be the cause of the "Missing plugins" error. Create a new administrator account, log on to it, and then try to start Illustrator in the new account."
The problem is, I don't know how those solutions would work with a thinapped application. I was running the Thinapp on the test machine in another account also with full privileges, the fonts are all there and I don't think that the preferences are corrupt because it is a "fresh" installation.
Oh and I noticed that the issue also occurs on a Windows XP SP3 32bit test machine.
Any further help is much appreciated.