There is one other scenario which we have encountered.
If you have Financials Bank Accounts linked to your Online Bank Accounts in Company A, then while they are still linked, you delete Company A. Next you have created Company B, and you rename that company to be Company A. You may now encounter the original error message when attempting to link your Bank Accounts to Online Bank Accounts in your new Company A. Here is the error:
"com.yodlee.core.usermanagement.UserNameExistsException
Failed to register the consumer.
Try the action again or specify the consumer credentials manually.
The consumer credentials are not valid."
This is due to an orphaned record. It is necessary to open a support incident with the Dynamics 365 for Finance and Operations, Business Edition support team so that we can delete the orphan record. Another option is to not use the "Company A" name as this is a part of the orphaned record.
For future reference, unlinking all of the Bank Accounts before deleting a company would avoid this issue as well.