gistfile1.js

// Yours
function repeatUntilSuccess(promiseProvider) {
    return new Promise(function (resolve, reject) {
        var counter = 0;
        function run(failedResult) {
            var p = promiseProvider(failedResult, counter++);
            if (p instanceof Promise) {
                p.then(resolve).catch(run);
            } else {
                reject(p);
            }
        }
        run();
    });
}

// let's remove the bad instanceof check 
function repeatUntilSuccess(promiseProvider) {
    return new Promise(function (resolve, reject) {
        var counter = 0;
        function run(failedResult) {
            var p = promiseProvider(failedResult, counter++);
            Promise.resolve(p).then(resolve).catch(run);
        }
        run();
    });
}

// now, we don't really need the `new Promise` either:
function repeatUntilSuccess(promiseProvider) {
    var counter = 0;
    return Promise.resolve().then(function run(failedResult){
        var p = promiseProvider(failedResult, counter++);
        return Promise.resolve(p).catch(run); // and.. the deferred anti pattern is gone!
    });
}

// but this is very very risky, since errors might be a syntax error or something like that which will become and infinite loop here
// so we want to retry based on a falsey return value and _not_ on rejection. Rejections are like exceptions and a real while doesn't 
// stop on exceptions (except in Python - but meh :P)
function repeatUntilSuccess(promiseProvider) {
    var counter = 0;
    return Promise.resolve().then(function run(failedResult){
        promiseProvider(failedResult, counter++);
        return Promise.resolve(p).then(function(val){ 
            return val || run(val);
        });
    });
}