Thanks for the good thoughts Dude111.
For others who are using Verizon Mifi I posted this issue in DSL's Millenicomm forum and got a response from stevewm who says:
"There is a ongoing thread on Verizon's own web forums where many others are running into this issue.
No one seems to know exactly where the problem lies. Its likely some routing issues in Verizon's own network... People with other 4G devices have chimed in similar issues."
I checked out the link and there is a 14 page discussion on this exact problem.
So thanks to stevewm and to everyone here who has pitched in to help me resolve (well not resolve but at least understand) the problem!