There's a guy here in Seattle who has done a bunch of fencing shoes, including several of mine which are probably the same adidas high tops you have. He charges $50 though, so once you add the shipping cost, you may or may not consider it worth the cost.
I can say he does a great job, and i've been entirely satisfied with his work. I even kinda like the grip pattern of the sole he put on a little better than the "stock" sole.
If you do get him to do it, ask him to take the new sole all the way up the heel, gluing it to the sanded down remaider of the old heel's rubber. He did that once for me, and once not, and I preferred it all the way up.
Page Dave Cobbler
3509 Evanston Avenue North
Seattle, WA 98103
206-632-8686
http://www.davepagecobbler.com/