It turned out that even though I unregistered the old vCenter with "cmsso-util unregister" prior to reinstall, a lot of stale services from the decommissioned vCenter were still present in PSC. This KB - VMware Knowledge Base - gives a hint, but it's not just vcenterserver service type that needs to be removed.
Just in case someone else would hit this issue:
1) you need to figure out the Node ID of your old stale vCenter, the KB referenced above gives you a clue how to do that.
2) Find the Service IDs of all stale services matching the old Node ID (in my case the stale Node ID was 0f3616d1-65cc-4a66-aa34-8d1bd5e44586):
/usr/lib/vmidentity/tools/scripts/lstool.py list --url http://localhost:7080/lookupservice/sdk > /tmp/psc_services.txt
services=($(cat /tmp/psc_services.txt | grep -B 3 0f3616d1-65cc-4a66-aa34-8d1bd5e44586 | grep -i "Service id" | cut -d " " -f 3))
3) Now that the Service IDs that you need to remove are in the $services bash variable, you can do the removal:
for i in "${services[@]}"
do
/usr/lib/vmidentity/tools/scripts/lstool.py unregister --url http://localhost:7080/lookupservice/sdk --id $i --user 'administrator@vsphere.local' --password 'your_password' --no-check-cert
done
4) restart vCenter services and once you log back in, the stale licensed asset entry for the old vCenter should be gone.