Algorithm

Assumes an alphabet of a-z, and that spaces ' ' sort before 'a'.

• Copy characters from the beginning of both strings until you reach the first difference or end of left string.
• Append character half way between left character (or alphabet beginning) and the right character.
• If the characters are consecutive: copy left character, then append character half way between next on left string and end of the alphabet.
• If the next character on the left is one or more Zs, copy and append character between first on-z and end of alphabet.
• Never create a string by appending A to the left. If you end up doing this, add an additional character half way between the start of alphabet and next character from right string.

Code

int midstring(const char *prev, const char *next, char *buf) {
    char p = 0, n = 0;
    int len = 0;
    while (p == n) {                                           // copy identical part
        p = prev[len] ? prev[len] : 'a' - 1;
        n = next[len] ? next[len] : 'z' + 1;
        if (p == n) buf[len++] = p;
    }
    if (p == 'a' - 1) {                                        // end of left string
        while (n == 'a') {                                     // handle a's
            buf[len++] = 'a';
            n = next[len] ? next[len] : 'z' + 1;
        }
        if (n == 'b') {                                        // handle b
            buf[len++] = 'a';
            n = 'z' + 1;
        }
    }
    else if (p + 1 == n) {                                     // consecutive characters
        n = 'z' + 1;
        buf[len++] = p;
        while ((p = prev[len] ? prev[len] : 'a' - 1) == 'z') { // handle z's
            buf[len++] = 'z';
        }
    }
    buf[len++] = n - (n - p) / 2;                              // append middle character
    buf[len] = '\0';
    return len;
}

Code for renumbering strings

Generate a set of average length strings, after you've screwed up your namespace with long strings.

function seqString(num) {
    var chars = Math.floor(Math.log(num) / Math.log(26)) + 1;
    var prev = Math.pow(26, chars - 1);
    var ratio = chars > 1 ? (num + 1 - prev) / prev : num;
    var part = Math.floor(ratio);
    var alpha = [partialAlphabet(part), partialAlphabet(part + 1)];
    var leap_step = ratio % 1, leap_total = 0.5;
    var first = true;
    var strings = [];
    generateStrings(chars - 1, "");
    return strings;

    function generateStrings(full, str) {
        if (full) {
            for (var i = 0; i < 26; i++) {
                generateStrings(full - 1, str + String.fromCharCode(97 + i));
            }
        }
        else {
            if (!first) strings.push(stripTrailingAs(str));
            else first = false;
            var leap = Math.floor(leap_total += leap_step);
            leap_total %= 1;
            for (var i = 0; i < part + leap; i++) {
                strings.push(str + alpha[leap][i]);
            }
        }
    }
    function stripTrailingAs(str) {
        var last = str.length - 1;
        while (str.charAt(last) == 'a') --last;
        return str.slice(0, last + 1);
    }
    function partialAlphabet(num) {
        var magic = [0, 4096, 65792, 528416, 1081872, 2167048, 2376776, 4756004,
                     4794660, 5411476, 9775442, 11097386, 11184810, 22369621];
        var bits = num < 13 ? magic[num] : 33554431 - magic[25 - num];
        var chars = [];
        for (var i = 1; i < 26; i++, bits >>= 1) {
            if (bits & 1) chars.push(String.fromCharCode(97 + i));
        }
        return chars;
    }

}
document.write(seqString(1600).join(' '));