I have absolutely definitely been to every location between -7,-7 to 7,7 (twice) without finding it. (First 2 chaches found successfully.)
It should be working fine, it's location resets every hour or whenever someone else finds one so it can be a bit difficult sometimes to find one
Did find it in the end, VERY glad I don't have to do that again though... I don't know how many players have actually been through this process successfully, but having to fastidiously search up to 224 locations with the possibility of still not finding it is a bit off-putting!
A suggestion - perhaps when doing these searches you could have a "hot... warm... cold... freezing" status to give the player at least some vague notion where they should head?