I too have found I needed to set the profile, see my comments: Nova R410 (Cat-M) Issues (Troubleshooting tips and tricks and known issues on the R410 Nova + user feedback on issues) - #5 by AndrewGifft
For a while I thought it was necessary:
Note, until this post, I felt setting UMNOPROF to be required to connect. I remember leaving a SARA-R410M-02B on for over a day without connecting and setting UMNOPROF and rebooting it connected within minutes.
Nearly exact same behavior you describe. I have had simcards connect without setting the profile after 1-2 hours of waiting but from both your and my experience it seems that may not be 100% reliable.
The downside of setting the profile ofcourse is you lose some of the benefit of “Hologram works on pretty much any carrier” unless you write more sophisticated code to try Verizon and then hunt on other profiles if Verizon fails.