You don't even need to go that far. Make it a federal crime to file false reports on this (Oh wait, it probably already is) and then go around doing spot checks all over the country to enforce it. Go to one of those nice ISP websites and check if broadband from them is available at 'your' address by filling in random addresses in the regions those ISPs claim they are available.
Then go around some of those places, knock on doors or make appointments to come by and test their actual connection speed.
After a few billion dollar fines and some execs jailed for this bullshit, the situation will rectify itself. Good luck getting the government to go that far though.