En softonic tienes muchos programas especializados en desinstalaciones. Sino siempre puedes usar regcleaner o similares para borrar las cadenas "office" y demas a lo bestia, eso si, exponiendote a joder medio windows.
De todas formas, yo lo que haria seria reinstalar office y despues desinstalarlo bien.
PD: seguro que hay programas de estos tweaks de windows 7 que te dejan eliminar los items del menu "nuevo".