Rickstarr is right about doing everything yourself. Credit repair companies are all a scam and they can do no more than you. But he's wrong in saying that if you make a payment on a delinquent account it will reset the credit bureau time clock back to 7 years.
Both Equifax and TransUnion go by the date of original default of the debt. Provincial legislation may use the term :"date of last payment," but the bureaus don't. By the way, collections are reported for 6 years in BC and Alberta from the date of FIRST default, not 7 years.
http://www.fcac-acfc.gc.ca/eng/publications/CreditReportScore/UCreditScore-eng.asp
If you make a payment on a debt in 2010 which went first went belly up in 2005, it still comes off your credit report in 2011. At least it's supposed to. Regretfully, collection agencies and debt buyers might put the wrong date on an account to keep it going. Or they can load up your credit file with hard inquiries contrary to bureau policy and/or provincial laws. Then you've got a problem.
Trying to get the bureaus to correct information is notoriously difficult. Even if you send them registered letters with account statements verifying the corrected information, likely nothing will get done as Footloose discovered. They merely claim "to have contacted the creditor and verified the information currently on file was accurate as is." Stop me if you haven't seen a gazillion of these letters.
In reality, nothing has been done because they get countless thousands of disputes every year, and so they handle them with a few templated forms to cover each category of complaint. The form letter you get back will be the same one thousands of others receive. Even if you send in 100 pages of documented proof, nobody will read them, and you'll still get back the same form letter.
Consumer letters are junk mail to them. The boilerplate responses merely serve the purpose of lamely maintaining the veneer they're following the provincial consumer protection acts.
The claim that everything on your credit report must be accurate, complete and verifiable or must be removed in 30 days exists only in theory.
The bureaus get thousands of bluff letters each year from consumers or so called credit repair outfits demanding they verify millions of bad debts found on countless credit reports. Consumers and credit repair outfits play this card because they think they can bamboozle their way out of bad debts being reported. The bureaus circumvent that tactic with form letter responses. Unfortunately, those with legitimate complaints get lumped in with them.
Effectively, we now have something worse than a reverse onus law. The consumer must prove their innocent, not the other way around. Even if the consumer can prove they are innocent, the bureau still won't give them a fair trial.
Next, you may, as so many others have, file a complaint with Comsumer Protection, True, they probably won't do much either, but you can get mediation and a hearing over the dispute. At least it forces the bureaus to read what you've submitted and take the appropriate action.