Is this an internal, serial, or USB modem?
It sounds like either the instalation is not completing all the way, or your registry isn't recording the information on the new hardware.
When you detect the modem and after you install it, does it show up in device manager? If it shows up with no problems and then dissappears from there after a reboot it sounds like registry.
Also, if you are using a USB modem the system will often not recognize the device if it is plugged into a different USB port than it was installed on. IE if you had it in port 1 when you installed it, but later move it to port 2, you will have to reinstall it on port 2.