Hi @Anonymous,
I think your thought is correct. When you created a SP list connection within your flow, if you delete the SP list, the flow would lose connection to this SP list.
Even though, you re-created a SP list with same name as before, the flow would not recognize this SP list automatically. Actually, the SharePoint connector within Microsoft Flow find the specific list via a series of GUID string (e.g. '173056e5-b540-49eb-83be-c4680cbbf248').
The GUID string (e.g. '173056e5-b540-49eb-83be-c4680cbbf248') is generated by SharePoint automatically when you created a list within your SharePoint Site. In addition, the GUID string identify a List within your SharePoint Site uniquely. Although, you created a SP list with same name as before, the GUID string is different. So the flow could not recognize the new created SP list automatically.
Currently, you could only re-choose the new created SP list within your flow manually to achieve your needs.
If you would like this feature to be improved, please submit an idea to Flow Ideas Forum:
https://powerusers.microsoft.com/t5/Flow-Ideas/idb-p/FlowIdeas
Best regards,
Kris