Depends what they tried on them? I've had good results with Bilt Hamber Korrosol on very heavy baked on brake dust on an Evo before, took about 4-5 applications. Can't remember if I did use a bit of wheel acid on them in the end though, don't believe so though.
Alternatively, you could use wire wool. Obviously it will scratch the finish to an extent, but can be an improvement over the brake dust look.