The problem stems from allowing users to generate their own score data device-side. This would be a lot harder if all the score related calculations were done server-side and then posted to the score-board (I don't know how your app works, so I can't recommend a specific technique).
I think the BEST thing you can do is record data about HOW they got the really high score for review later by you. That may be impossible depending on your game's structure. It also might be forge-able depending on your games structure. For example, some game scores are impossible to get in-game just due to the physics on how the game works. This in my opinion is your best defense against it. Sadly, that requires monitoring it all the time....
Also, even if you can verify fake scores, someone could continually forge fake scores all day long and you'll never be able to keep up with it. Someones score submission bot will win in the end. It's not human, you are. It can post fake scores all day, you can't watch for fake ones all day, you can't verify 1000s of fake submissions. Trying to verify anything that is generated user-side (such as device ID, app being installed, etc...) is pointless. It can be forged. IP addresses are meaningless too. Your app is a on a mobile platform that can get a brand new IP all they want from the cell company. Tracking single legit real users is very hard if someone wants to hide from you because of this.
Maybe you can have some kind of app purchase verification with the help of Apple too. That would make it easier for you to ban offenders. They would have to pay you to forge your leaderboard, lol.
That's just my 2 cents, I hope it helps.