A certificate system could work, but really all that's needed is traceability.
If I complain about a call, that should be trackable to the origination carrier and account, and if either one gets too many complaints, it gets thrown off the network (and other penalties).
Actually there is some standardization activity trying to do this. It does not solve the main problem: if you let the originating carrier sign the caller id, you still have to trust that carrier to really check if the caller is authorized to use it. Number portability prevents you from using certificates older than 24h.
The issue is that the PSTN is essentially a huge, worldwide message queue to which pretty much any telco can connect around the world, including shady ones - even if US law actually does fight spoofing, how do you prevent telcos from other countries from continuing the abuse?
Cryptography is needed - when a carrier leases you a number, they give you a certificate with which you can sign other carrier’s certificates if you want to let them use that number as caller ID. Every carrier on the call chain should verify call’s signatures against that and discard any calls with missing or invalid signatures. That will stop malicious spoofing while allowing its legitimate use, just like email where you can use SPF and DKIM to nominate any email provider to be able to send on your domain’s behalf.