Don't you have to periodically update your phone's internal list of active towers with Verizon? I recall doing this once for my wife's phone and it immediately got better signal strength.
edit: I found the Verizon FAQ concerning *228
Here's the text of it:
Why do I need to perform this update on my wireless phone?
By performing this update your phone will stay on the Verizon Wireless network and/or digital service whenever possible. Also, for most price plans after 2/1/2002 the phone roam indicator will turn off/on in accordance to the price plan you have chosen.
What are the steps I need to take to complete this update?
The following are the steps you need to take to complete the update:
1. Power on your Verizon Wireless phone
2. Dial *228 from your home digital coverage area, followed by the SEND key
3. When prompted, press option #2, to update your phones roaming capabilities (This process may take up to 2 minutes)
4. Once completed, a confirmation message will be played, and a message will display on the phone screen.
What if the update fails to complete successfully?
If for some reason the update does not complete successfully, please try again at a later time. If the problem persists, your phone may not be capable of this update process.
What benefits will this update provide?
Benefits of this update may include:
Longer battery life
Fewer dropped or blocked calls
Clear, crisp connections in even more areas across the United States
Roaming indicator will reflect the price plan you have chosen (available on most price plans after 2/1/2002).
How often do I need to perform this update?
This update should be performed every three months, and/or after changing price plans.
How much will this *228 call cost me?
This call is offered FREE of airtime charges from Verizon Wireless.
When can I perform this update?
You may perform this update at your convenience. This FREE software update is available to you 24 hours a day, seven days a week!