My iPhone 5s is suddenly dropping calls, "searching" off and on in places where I never have had any trouble getting service EVER, and today got a screen message saying phone had to be activated. I turned it off and back on and it worked fine for a few minutes, then went into searching mode. Happened at two different locations. I've been using it for over a year with no problems anywhere. I recently updated software and am on iOS 8.1.2
How can I tell if it Is it a device(phone) issue or a Verizon issue?
Have you tried resetting your network settings? If not, try there and see if that yields any results. Often times a quick reset of network settings fixes similar problems.