I had a similar problem in that British Gas sent my'debt' on to a collection agency, even though they had my forwarding address. The bill related to a property that I had sold 13 months before and, as far as I knew, paid all bills. The Agency took all the detail, spoke to a person at British Gas whose name I supplied, realised it was a misunderstanding & I never heard anything more [not even an apology, but that is a different matter].
If you have everything written down [dates, times, names of who you spoke to] I would immediately call the solicitors and give them this detail - together with the date and amount paid. The trouble is, solicitors charge for their letters and this is usually added to the debt - so you need to stop it all now. If you do not have everything, the date payment was made and the amount would suffice and solicitors like to see this on a Bank Statement.
As I said, you MUST do something now. I know that the people at AOL are nice, but they won't pay any fees that you may incurr and I bet that the responsibility will be made to be yours to call to correct their mistake. Remember though that AOL 'sold' the debt to the Collection Agency, who then employed the services of the solicitor. I also bt my last $ that AOL do not have a procedure to call the Agency to advise that they have now been paid, so they carry on regardless.