I benchmarked the non-golf solutions. The results show that tye's solution is the fastest by quite a margin.

Test input is 'XYZZY'                             

Benchmark: timing 1000000 iterations                     
     japhy: 28 secs (28.21 usr +  0.01 sys = 28.22 CPU) @ 35435.86/s)
    japhy2: 23 secs (23.57 usr +  0.00 sys = 23.57 CPU) @ 42426.81/s)
    japhy3: 22 secs (21.87 usr +  0.01 sys = 21.88 CPU) @ 45703.84/s)
       jmn:  8 secs ( 7.26 usr +  0.01 sys =  7.27 CPU) @ 137551.58/s)
    merlyn: 20 secs (20.54 usr + -0.02 sys = 20.52 CPU) @ 48732.94/s)
    petral: 22 secs (22.47 usr +  0.01 sys = 22.48 CPU) @ 44483.99/s)
       tye:  5 secs ( 4.84 usr +  0.00 sys =  4.84 CPU) @ 206611.57/s)
           Rate  japhy japhy2 petral japhy3 merlyn    jmn    tye
japhy   35436/s     --   -16%   -20%   -22%   -27%   -74%   -83%
japhy2  42427/s    20%     --    -5%    -7%   -13%   -69%   -79%
petral  44484/s    26%     5%     --    -3%    -9%   -68%   -78%
japhy3  45704/s    29%     8%     3%     --    -6%   -67%   -78%
merlyn  48733/s    38%    15%    10%     7%     --   -65%   -76%
jmn    137552/s   288%   224%   209%   201%   182%     --   -33%
tye    206612/s   483%   387%   364%   352%   324%    50%     --

Test input is 'XYZZZ'

Benchmark: timing 1000000 iterations
     japhy: 28 secs (28.30 usr +  0.00 sys = 28.30 CPU) @ 35335.69/s)
    japhy2: 22 secs (22.45 usr +  0.02 sys = 22.47 CPU) @ 44503.78/s)
    japhy3: 22 secs (21.97 usr +  0.01 sys = 21.98 CPU) @ 45495.91/s)
       jmn: 27 secs (25.95 usr +  0.00 sys = 25.95 CPU) @ 38535.65/s)
    merlyn: 18 secs (18.30 usr +  0.00 sys = 18.30 CPU) @ 54644.81/s)
    petral: 18 secs (18.69 usr +  0.01 sys = 18.70 CPU) @ 53475.94/s)
       tye:  5 secs ( 4.85 usr +  0.00 sys =  4.85 CPU) @ 206185.57/s)
           Rate  japhy    jmn japhy2 japhy3 petral merlyn    tye     
japhy   35336/s     --    -8%   -21%   -22%   -34%   -35%   -83%     
jmn     38536/s     9%     --   -13%   -15%   -28%   -29%   -81%     
japhy2  44504/s    26%    15%     --    -2%   -17%   -19%   -78%     
japhy3  45496/s    29%    18%     2%     --   -15%   -17%   -78%     
petral  53476/s    51%    39%    20%    18%     --    -2%   -74%     
merlyn  54645/s    55%    42%    23%    20%     2%     --   -73%     
tye    206186/s   484%   435%   363%   353%   286%   277%     --
[download]

Update 2: Added petral's solution.

As a general observation. 97% of the Base36 range can be handled with a simple substitution of the last character in the string. This is the test case represented by 'XYZZY' above. The remaining numbers in the Base36 range (those ending in Z) require more work. This is the test case represented by 'XYZZZ'.

All of the above solutions could be optimised for the substitution case. The Z increment is therefore the governing case in determining the speed of the solution.

What's nice about tye's solution is that it takes these factors into account. He wrote it to be fast and it was.

John.