There have been some Verizon phones that will say this every time you turn on the phone with a non-Verizon sim card. This not necessarily mean that the phone is locked to Verizon. The Verizon Moto E4 is a perfect example of this and you can dismiss this message and then continue to use the phone.
The wording for Verizon uses to tell you that the phone is locked after inserting a non-Verizon sim card is different than the normal "insert unlock NCK" or similar messages. I can't remember the exact on-screen wordiing.
@computergeek541 really? Yikes what a pain. Verizon, ugh. I wonder if there's a way to avoid that by setting the CSC or something?
Yup, the Verizon Moto E4 will provide a friendly reminder every time that you turn the phone if the sim card in it isn't a Verizon one. This happens even after you unlock the phone.
In the case of the Verizon Moto E4, there was never a bootloader unlock available for it. That means that you couldn't root, or even install any other software rom.
In the case of HTC, they've used something called an RUU file in the past. They were Windows executable files and you would connect your phone with a USB cable to flash the factory rom images. In some cases, you could install another carrier's or even a factory sim unlocked rom, but you would first have to set one of the phone's settings to S-off so that you could install other carrier roms or even downgrade software versions. I am uncertain if this is possible with the Verizon HTC One M8.