Hace algún tiempo necesité hacer esto mismo y encontré en algún lugar de internet un ejecutable que me permitía hacer esto. He buscado la URL de dónde lo bajé y ahora no recuerdo, pero bueno, por suerte existe rapidshare y ahí te lo subí para que lo utilices. Este es el enlace para la descarga:
http://rapidshare.com/files/135620728/StartBt.zip.html
Este ejecutable tiene tres parámetros: /hide /show /remove
Con el primero ocultas el botón inicio, pero si haces clic en el borde inferior en la esquina izquierda de la barra de tarea te sale el menú inicio aunque no veas el botón. El segundo parámetro sirve para volver a aparecer el botón cuando se esconde con hide y el tercer parámetro /remove fue el que utilicé porque cuando ocultas el botón con este parámetro no hay quien lo haga aparecer ni tampoco se muestra el menú inicio hagas clic donde hagas.
La solución que encontré para que a los usuarios se les ejecutara y no a los administradores fue ponerlo en la llave de registro HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\Curr entVersion\Run como un nuevo valor alfanumérico, de esta forma se ejecutaba siempre que alguien iniciaba sesión en la PC. Pero para evitar que se ejecutara también a los administradores les quité el permiso NTFS de ejecución al ejecutable para los administradores y así resolví mi problema que es bastante parecido al tuyo.
Saludos y suerte!
http://zenkius.blogspot.com