One issue could be - if the users have roaming profiles, and their workstations are *not* running Outlook 2010, they will get this prompt every time. Outlook 2010 profiles are not compatible with older versions.
Another cause could be permissions on the registry keys on the TS - if the users don't have permission to modify the office registration key, it won't write to the registry that they have already went though this process.