Outlook Mail API: Error 429 after 500 message 'move' requests

Yes, 429 is the HTTP error code "Too Many Requests - The user has sent too many requests in a given amount of time ("rate limiting")."  The HTTP specification doesn't specify how the server identifies the user, nor how it counts requests, so the implementation might hit a limit earlier than you would otherwise expect. 

We don't have access to the details of the implementation, and it might change from time to time, so depending on how it is implemented you might also get a 500 thrown from time to time as well. I am not surprised that you are getting rate throttling even though the headers claim you have a few requests to spare, but I agree that the very precise Rate-Limit-Remaining header is unhelpful if it is not accurate, and worth raising as an issue.