We encountered a similar issue. In our case, after successful authorization, the AccessToken can be used normally. However, after a period of time, attempting to use it again results in the error message “Invalid API key or access token (unrecognized login or wrong password),” even though the store has not been logged into nor used the Shopify API during this period. After re-authorizing, we found that the AccessToken is the same as before, but it becomes usable again. We are using an offline mode AccessToken.