Are your workstations running Vista Home Premium?
If you're on XP I doubt that you'll have the same problem.
Basically, what I would do is right-click on a PHP file (CGI, PL, HTML, CSS, etc.) and select Open With, select Notepad++ and set it as the default editor for that file. Today I found that in Notepad++ preferences you could select file types to associate with. So it looks like doing it this way put the link back in to the right-click New menu. I don't know if repairing MS Office 2003 had anything to do with it as stupidly I did both at once to save time.
(Notepad++ 4.7.5)