just to confirm that this is still going on when using the REST API.

Same here using the REST API. I tried generating new keys or adjusting the validity window the access tokens, but none seems to work to avoid the error messages. It's something that clearly would need to be fixed if the service would come out of beta, especially that effectively we get charged for using this API.