Voodoo Extreme report that Max Payne works under Windows 2000/XP
Max runs happily on Windows 2000 and Windows XP and even supports the XP´s "Switch User while leaving all your software open" features (unofficially since XP isn´t out yet).
While on the subject, the game has an option to enable/disable task switching (Alt-Tab, Ctrl-Esc etc). It´s disabled by default. Mod makers etc probably want to run the game in a window while taskswitching to check documentation etc, but a lot of end-users were accidentally pressing Alt-Tab and ended up on the desktop. Duh.