Ve a la siguiente ruta: C:\Archivos de programa\Max Payne e instenta buscar y localizar el desinstalador, por lo general se llama "Uninstall". O bien, si tienes el juego en un CD o el instalador en tu PC, ejecutalo y te dará las tres opciones: Desinstalar (Remove), Reparar (Repair) o Modificar (Modify) y le das a Desinstalar o Remove.

P/D: Puede que el cambio de Sistema Operativo o el formateo de dísco haya borrado el desinstalador del juego pero sería raro que solamente borre éste archivo. De todas formas no te hagas problema, igual podemos desinstalarlo manualmente si no lo encuentras sin dejar ningún tipo de rastro del maldito juego.

Besos.