I know it is only a partial solution, but I saw with some companies that LinkedIn provides a way to verify a user works at such a company. This is done via sending an email to a company domain email address (supposedly yours that you provide), and then approving it from your work laptop. I guess the administrators of the company account on LinkedIn can determine which domains are allowed for this.

The only way this could be abused is if the administrator accounts on LinkedIn itself get hacked and temporarily other email domains are added to the whitelist (or if an approved user themselves got hacked on LinkedIn [or their work email for that matter]). These are all the usual vulnerabilities in any system.

I understand that it would be too extreme to only allow users to claim they worked at a company if this verification is done, but maybe putting a warning if you get a message from a recruiter/someone that has not verified they work at their 'present' company could go a long way (instead of right now tucking away the verified logo quietly on their profile page).