Hello again @BCBuizer ,
Please excuse the late reply, I was somewhat busy.
Regarding the issue at hand, I'll be honest, it fixed itself. And I'm not even sure why.
I just opened the app and checked the flows, and it was there, for no apparent reason.
I also got into a call with Microsoft support, and the supporter determined that the issue was perhaps caused by permissions regarding the connections used in the flow, but that was never confirmed.
I did check the link (https://powerusers.microsoft.com/t5/Building-Power-Apps/Unable-to-add-flow/td-p/1603538) that you provided in your latest reply, however the issue there is different from my case, even though the error message is the same.
I will note however, that during this whole ordeal, I actually tried to create a duplicate of the flow, and I did succeed in adding that duplicate to the solution, so this could technically be a way to get around this problem, however I did not want to do so as I was hoping we could find a solution for future uses too.
I wanted to thank you again for your time in trying to help.
Good day.