I'm not sure what Verizon meant, but if you have put your old iPhone into Lost Mode then do not delete the device from your Apple ID account as that will remove Activation Lock, and whoever finds it can restore it (they can't access your data, but they could restore it and potentially use it with a new SIM). Leave it in Lost Mode and associated with your Apple ID. If it is ever found, then no one can access it or make use of it, period. More info:
If your iPhone, iPad, or iPod touch is lost or stolen - Apple Support
and:
https://support.apple.com/kb/ph19299?locale=en_US
https://support.apple.com/kb/ph2700?locale=en_US
If you have a recent backup of your old iPhone, set up your replacement with this backup, that's all you need to do. If you already set up the new iPhone, then restore it and choose your old iPhone's backup when finishing up.