Cheepest thing to do: get a good diagnosis from a vet, not trying everything under the sun, as you can see its wasting money. Get a specialist if need be, go to a horse hospital, get a second opinion ect. A nerve block is pretty inexpensive and you best bet to see what leg(s) and were the lameness is in the leg(s). I paid about 30 for the block itself, but yo also have to factor in having a general exam, and a vet call. A flexion test is also an inexpensive way to see what area is lame.
Also assess if the farrier is indeed dong a good job. Just because you had him barefoot and shod dosent mean anything unless its done right. Maybe post some video of his movement?