Have you tried holding the "#" as the phone starts up (holding it down at any other time doesn't do anything, I believe). This almost always works for me:

reboot the phone and immediately hold down the "#" key. The speaker/headset/mute lights should cycle and the display should read factory reset sequence detected (or something similar, I dont remember offhand). While this is on hand, quickly key in the following number: 123456789*0#

It should then ask you on the screen if you want to keep the network configuration, enter the number corresponding to your choice and you should be on your way to a defaulted phone.

Sometimes, however I have had stubborn phones that don't want to reset. What I do in that case is go into the network configuration and try to determine what the TFTP server is. When you know what the server IP the phone is looking for you can set up a TFTP server on your network with the same IP and config files of the locked phone. That way when the phone boots it downloads your config files and thus loads your password and other settings.