So my company is already mandating iOS 17.3 and up until now we had a total of around 20 users that had this issue.
Last user that came in had 50k+ contacts in iCloud and currently we're using this workaround:
1. The user logs in with their Apple ID on a Mac
2. Open the contacts app on the Mac and wait until it shows the number of contacts as on the iPhone
3. Look for duplicates and merge all the duplicates (99% go down to under 1k contacts)
4. Export the vCards from contacts app on the Mac
5. Disable on the iPhone the iCloud Contacts sync
6. If the user has a Google Account, import the contacts to the Google Contacts and use that option on the iPhone (It does a mirroring of the contacts to the iPhone instead of copying them but keep the iCloud Contacts off)
7. (Try) To delete all the contacts from iCloud.com (Depending on the number of contacts it'll just "fail" on you)
8. Reboot the iPhone and try it out.
Apple Support were not happy with this workaround and they "forced" me to wait to find another way around (was over 1h with them on the phone)... They didn't 
In any case, hope this helps some of you guys here. Google Contacts is the way to go (until now).
I guess Apple is too busy with the Apple Vision Pro so that's why they're not prioritizing this bug... 
Should I find any other way around, I'll let you guys know.
Until then, cheers 