I wish that Mark did not mark "recreating the Flow" as the answer for this post because this bug still persists.
The closest way I've been able to recreate this issue on a consistent basis is to create a flow with a given set of connectors (SharePoint, OneDrive, etc.). The Flow can work flawlessly and seem great. Then, if I go back and now want to add an additional connector (custom or OOTB such as Outlook) I will get an error that the given connector is not available. It'll read like the following:
Unable to process template language expressions in action 'Send_an_email_notification_2' inputs at line '1' and column '2505': 'The template language expression 'json(decodeBase64(triggerOutputs().headers['X-MS-APIM-Tokens']))['$connections']['shared_sendmail']['connectionId']' cannot be evaluated because property 'shared_sendmail' doesn't exist, available properties are 'shared_excelonlinebusiness, shared_onedriveforbusiness, shared_sharepointonline'. Please see https://aka.ms/logicexpressions for usage details.'.
The Flow originally was created with SharePoint, Excel Online, and OneDrive (as seen in the available properties listed in the error). Then once I went to add the Send Mail connector a week later to just send a simple notification email, it reports that it "cannot be evaluated..." because the property / connector doesn't exist....
BUT I JUST ADDED THE CONNECTOR RIGHT TO THE FLOW. HOW IS IT NOT AVAILABLE?!?
Flow absolutely has a bug handling connectors (seems to be consistently related to OneDrive for Business associated Flows if that helps narrow it down). Please don't tell me to just re-create it.
