Snail mail is very hard to prove that correspondence happened. State law requires that I dispute their claims within 30 days via snail mail, which I did. They then have to provide documentation within 30 days via snail mail, which they didn't. They should be fined for that, but all I can prove is that I mailed them something within 30 days, and everything else is he-said-she-said. I prefer to tell them I'm recording the phone call. Unfortunately, my state's laws don't require they cooperate that way, and many just hang up immediately. It does stop the harassment, though.
The US postal service provides certified delivery. It requires a signature and proves delivery. You show your proof, and if they can't show theirs, you win in small claims. At least, that is the idea...
you should read patio11's recent post on dealing with this kind of thing. He's talking specifically about dealing with credit agencies, but the same paper trails are likely to be the standard way of dealing with any legal hassles. Also my understanding is that the burden of proof is on the creditor/collector to prove you owe something, so having a paper trail showing how you dealt with things in a timely manner is going to make you look better and avoids the he said she said problem.