RoPo, have you printed out fliers?
It is what I would do. Then I would drop one off or send it to all the local veterinarians and farriers, both are lucrative in the horse industry and I'm sure someone is sure to run across your horse. Then I would visit all the local feed stores and give them one as well, also explaining what is going on.
It might not get Max back directly, but a visiting farrier or vet might be able to get a location and observation of him. And everytime he goes to the feedstore, he'll get sick and tired of being painted a horse thief.
You did make sure to keep in regular contact with the local sales, they see many animals and a flier a few weeks old might start to be overlooked. But, by calling and talking to them regularly, they'll know you are still searching and you want them to keep up the vigil.