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 );
	} )
}

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 :)