Paid collections tend to not budge off one's report until 7.5 years after DOFD. Damage is supposed to lessen over time, but I can point you to a LOT of people who ain't seen the damage lessen UNTIL it hits 7.5 years and goes bye-bye.
For this reason, I stand by my advice that one should NEVER pay a collection outside of a PFD unless you absolutely have to. Paying a collection does neither your credit score nor your bank account any good.
You can head over to CreditInfoCenter, and I can point you to a couple of threads on fighting paid collections. But odds aren't good.