Issues like T106339 are caused by GitHub's API rate limiting. The limit for anon access to the GitHub api is 60 requests per IP per hour.
The current rate limit can be checked with curl:
$ curl -sD - https://api.github.com/rate_limit | grep '^X-RateLimit' X-RateLimit-Limit: 60 X-RateLimit-Remaining: 60 X-RateLimit-Reset: 1437527145
The generic solution to this issue would be to document the process of creating a GitHub auth token and configuring Composer to use it. A possibly nicer solution would be to talk to GitHub and see if we can get a higher limit for the IP address range that is seen by GitHub as the origin of Labs Composer requests.