Complaining to your state's Attorney General might also be effective, depending on state law and your AG's priorities with regard to enforcing it.
If you can prove you suffered actual damages due to a fraudulent job posting, you could probably go after the company directly, either as an individual plaintiff or as part of a class action.
First off, you can't enforce it without making tradeoffs. To some people, the tradeoffs will be acceptable, to others they won't.
One method would be to require a deposit on job postings. Make it costly to post, but return the money when it's taken down - same concept as a bottle deposit.
Depending on the cost, this may or may not unequally impact small businesses - though one could make the cost proportional to the companys employees.
