Instead of using a fixed backoff, just use a token-bucket algorithm. Try a few requests every now and then and have each successful request enable another retry.