Hi Chris:
Sorry to hear this, it can be a lot of trouble to recover :(.
Names are stored on the sonoff's themselves so typically should recover if AM data is lost. However if it was a power outage the MppDevices will reset their data if there are multiple outages in a short period (you can disable this by setting "CycleRecovery" to 0. Usually when this happens to me (though it's more often with the mqtt2zigbee hub) I can use AM to rename the device (since AM will have the name and not reset it if the device reports a null name) but in your case of course this won't work.
It sounds like for AM the app data was cleared? Maybe an android problem, or something with the memory chip? Unfortunately there's no easy way to recover from that. Good you had a rules backup which I expect is most of the effort. But you'll need to go into the other settings to restore them as needed (use the AM Server setup steps on my site as a guide).
You might be able to track down some names by sorting the rules by device - you can see in the rules which devices they affect, it should show the right MAC names, and you'll be able to rename them using those as a guide. You could print the rules, and there's a "sort by device" option in the rule editor that might help.
For the TP Link devices, try restarting your router and then the devices - that will hopefully cause them to re-connect to the UDP multicast address they use and AM should track them down. If not you'll need to add them manually by IP, sorry :(.