They told me there is nothing I can do about it except change my number, which may incur additional costs, or I could try just waiting it out and it would probably stop.
Really? They can't do anything to stop it?
Caller ID is broken. It is trivial to spoof your own phone number because the receiving network assumes your honesty. You can tell them pretty much anything as far as your caller ID number, and they will relay it onto their customers.
Things can be done, but they are expensive and require everything to work together. The networks need to start a catalogue of who owns number blocks and then check inter-network calls to check that caller ID numbers are within the blocks provided (and bounce the call if they're not).
Additionally smaller interconnection networks (i.e. those that provided VoIP to telephone network interconnects) need to start putting caller ID information into their outgoing calls rather than allowing clients to do it, they can then verify that the client owns the number before allowing it.
The TL;DR: In the US only an act of congress can fix the current situation, but such an act would be expensive for phone companies and they have enough lobbying power to kill it dead.
So in answer to your concern: No. Verizon cannot stop someone spoofing your phone number, and in order to fix it for you they and other phone companies need a massive retrofit.
Anybody can generate custom outgoing caller ID numbers. That's not really a "spoof," that's just lying about who you are when you make a call.
Most phone "spoofing" would be if someone cloned your phone number and the phone was registered multiple times on the same network, so when you got a call, one or more of the phones would ring at the same time.
So no, it's not the carrier's fault, and it's not something they can control.
Designing an authentication/verification system is non-trivial but not impossible. There's just little political-will to actually do it.
As a side note, this is why you should always set a passcode on your voicemail box. Many folks have their voicemail set to skip passcode-authentication when they're calling in from their own cell phone number. The problem is: if someone spoofs your number and calls into your voicemail box, they've got unfettered access.
If I had a choice, I'd dump VZW in a hearbeat.