again its difficult to diagnose over the internet.
a factory reset is almost guaranteed to fix the issue but you are aware of the CONs (setting up you phone) of factory resetting. choice is yours. it could be any number of issues causing your dilemma.
you can also go to your carrier and have them smoke it over.