Por fin parece q encontré la solución.
Os la dejo aquí por si a alguno os ha pasado usando los servicios de terminal server con vuestras aplicaciones.
A hacer los accesos directos a la aplicación nunca utilizar unidades su no UNC, en vez de rutas como "C:\MiDir\MiExe.Exe" usad "\SERVIDOR\C\MIDIR\MIEXE.EXE" de la misma manera para el apartado iniciar en.
Por lo visto Windows 2003 server no puede resolver siempre bien la letra de la unidad, usando rutas UNC este problema se acaba y puede abrir perfectamente todos los ficheros.
Después de meses enfrentándome a esta problema y haciendo miles de pruebas lo descubrí por casualidad en la ayuda de ADS.
Espero q os sea de utilidad.
Saludos y Feliz 2011 a todo los miembr@s del foro