If the Pokémon with Illuminate is leading the party, the wild Pokémon encounter rate is increased to 200%.
Heatbutting Pokemon is still a wild encounter. Just make sure that the lead Pokemon has Illuminate. Illuminate just raises encounter rate to 200%, not a specific Pokemon's encounter rate.
Heracross are somewhat rare, so be patient!
Also, where are you searching? That might be why.
Here are the places:
- Route 33, 46, Azelea Town (Levels 2-5)
- Route 7, 11, 42, Vemilion City, Celedon City (Levels 11-17)
- Route 42, 44, 45, 47 (Levels 21-30)
- Route 28, Outside Mt. Silver (Levels 39-48)