I've wasted a few days trying to prove Thue's lemma with no success! The proof is absolutely easy if you just count. What 'red flags' are useful to give you a warning that counting might be more productive than other approaches?
I can start with one point, but it's more of a conceptual one and requires you to see the theorem in a bigger context: If you know that you cannot prove an existential effectively then counting is probably going to be involved. (You might notice that effective solution would imply fast algorithm for factoring or similar).