I'm unsure of the ProgId's (friendly names on CLSID Guids) used for Excel, but a quick look leads me to 'Excel.Application', as the type you might activate.
Take a look under HKEY_CLASSES_ROOT, on my machine I see "Excel.Application" and "Excel.Application.12", i suspect that you are activating "Excel.Application", if you look under the "CurVer" key under "Excel.Application" it points back to "Excel.Application.12", inspect this value on your repro machines.
My guess would be that you are starting Excel.Application, you may want to force it to start Excel.Application.9 if the prog id exists on your target machine.
Here is a little code sample:
Type excel9Type = Type.GetTypeFromProgID("Excel.Application.9");
Type excelType = Type.GetTypeFromProgID("Excel.Application");
if (excelType == excel9Type)
{
Console.WriteLine("Default Excel.Application is pointing to 'Verion 9' yay");
}
else
{
Console.WriteLine("Excel is installed, but it's not 'Version 9'");
}
if (excel9Type == null)
{
throw new InvalidOperationException("Excel.Application.9 is not a registered progid");
}
object excelApplication = Activator.CreateInstance(excel9Type);
// Cast excelApplication to whatever you are using as your application type.