Problem solved
I called apple and verizon (carrier in US). Verizon had to turn off visual voice mail on their end. Then restarted my iphone. Then they turned it one again and I had to restart my iphone again and it was working. Also backing up from itunes also started the problem all over again. So, next time I had the problem, I set the setting to "Set as a new iphone" and it has been working perfectly ever since. I do not use itunes to backup my iphone anymore, I use iCloud.