Status 429 Rate Limiting very frequent

One thing that may explain some of the disparity is that the web server may be able to make calls at a much faster rate than the Android device can.

Can you check what rate you are making the calls at when you see this though? And in any case, when you get one of these responses, the best thing to do is to check and respect the Retry-After header in the response, which should tell you how many seconds to wait before calling again for that user.