You have three options:
1) Send them a GW letter. A little goodwill can go a long way.
2) DV them. Yes, you can DV a paid CA and it sometimes works. The CA doesn't want to take the time or expense to validate so they delete. Modify the letters in here.
3) Wait 5 more years.
IMO, go for the DV first. Then GW after that.
Now, if you are going to DV, and because it is settled, make sure you have the paperwork from them to back up your position that is was settled. If you don't, try a GW.