What would I provide for the "Consumer Key" field for configuring an Auth. Provider if I am using Microsoft's Graph API to register my new app? I'm assuming my consumer secret is the equivalent to the 'client_secret' in the Graph API documentation, however for the consumer key, I'm not sure if that would be the authentication or refresh token that I generate.
The more that I look at this the more that I think the issue you're facing is that you have a connected app set up and you're trying to provide the information from the connected app to your third party partner. Which I believe is backwards.
The documentation you provided has a link to a more detailed explanation in the left panel (this document)
This document says that you have to set up an app on the MS side and that MS provides you with a secret. When you attempt to authenticate this is the secret you need to provide. Their documentation doesn't show anything about generating or requiring a key so I believe the answer to your question is You don't need to provide the consumer key, you need to provide the secret that Microsoft gives you, not the one SF gives you..
That being said, it seems that while you are using sf to make the callout, the issue does not actually exist on the SF side. You should attempt to contact support for the Microsoft Graph API for further assistance.