I don't believe VA Indianapolis or Mayo Hospital Perio programs are taking residents (did not see them in the ADEA PASS application). If I am incorrect, please someone correct me.
From my research, the best programs tend to be in the South (i.e. Texas, Alabama, North Carolina, Georgia). Paid programs, from what I've heard, provide little guidance but you gain a lot of experience as you are there to produce for the program...however, quantity does not mean quality.
For those still researching programs, consider the following: location, tuition, program director's credentials, number of residents accepted per year (generally, the more residents the more learning opportunities available as you can share and discuss cases), and the relationship with other specialities (you really want a program that has a strong tie with the prosth department).
Remember, not every perio program is the same. Some focus on classic perio, others on implants, or a mix of both. Determine what kind of periodontist you want to be, and choose a program that meets your goals.