> If it looks like it's going to take them much time or effort to deal with it they're liable to just throw up their hands and let you duke it out in small claims court.

In the US, couldn't you just make it their problem by not paying the disputed portion of your bill? (I haven't tried this myself and don't know how hard it is to dispute a negative credit report without going to small claims court in the end.)