Promiarra.js

function checkUrl ( url ) {
	function checkUrlInternal ( resolve, reject, url, count ) {
		count = count || 0;
		posts.find( { url: url } )
			.then( function ( posts ) {
				if ( posts.length ) {
					count ++;
					if ( count > 10 ) {
						reject( new Error( 'url:tooManyReplaces' ) );
					}
					url = url.replace( /-\d+$/, '' ) +'-'+ count;
					return checkUrlInternal( resolve, reject, url, count );
				}
				else {
					resolve( url );
				}
			} )
			.catch( function ( err ) {
				reject( err )
			} );
	}
	
	return new Promise( function ( resolve, reject ) {
		checkUrlInternal( resolve, reject, url );
	} )
}

3 indentações max, 9 linhas a menos, 1 biblioteca a menos para se preocupar.

var checkUrl = function(url, callback){
    (function loop(count){
        count = count || 0;

        if(count > 10)
            return callback(new Error('url:tooManyReplaces'));

        if(count > 0)
            url = url.replace( /-\d+$/, '' ) +'-'+ count;

        Posts.count({url : url}, function(err, docs){
            if(err) return callback(err);

            docs > 0 ? loop(++count) : callback(null, url);
        });
    })();
};

btw, use count() no lugar do find()

Dá pra fazer a recursão simplesmente retornando uma nova promise:

function checkUrl (url) {
    var max = 10, count = 1;
    return posts.find({ url: url }).then(function(posts){
        if (!posts.length) return resolve(url);
        if (count >= max) return new Error('url:tooManyReplaces');
        return posts.find({ url: url.replace(/-\d+$/,'') + '-' + (count += 1) });
    });
}

Mas a versão do @cranic faz a mesma coisa sem a complicação conceitual toda :)