Is there a more efficient way to do Base 32 encoding/decoding than this?
If you really want to chase those milliseconds then I would try following:   

1) I consider division operations as slow so I would avoid using two divisions if it can be replaced with one division and some easier operation:  

Function ToBase32(ByVal lInput)
    Dim lModulo, sTemp, lNextInput
    Do Until lInput = 0
        lNextInput = lInput \ 32
        lModulo = lInput - 32 * lNextInput
        sTemp = Mid(kBase32Digits, lModulo + 1, 1) &amp; sTemp
        lInput = lNextInput
    Loop
    ToBase32 = sTemp
End Function


2) In some other language I would use bit shift of course instead of diviosion/multiply. But as far as I got vbscript doesn't have bit shifting operators.  

3) Your FromBase32 method doesn't look optimal to me at all. I would replace those Replace and InStr calls with array of integers for letter chars. This array will contains corresponding base 32 numbers for chars. And you will be able to translate letter into number using array indexing accessor which is much faster operation than looking for a character in a string. Some pseudocode showing how to convert character sR into number:  

Dim sR;

// defining an array:
Dim charArray = [  10, // 'a' char
                   11, // 'b' char
                   ...
                   17, // 'h'
                   1 , // 'i' !! 
                   ...
                   0 , // 'o'
                   ...];

Dim lNumber;
if (sR &gt;= 'a' &amp;&amp; sR &lt;= 'z')
    lNumber = charArray[sR - 'a'];
else // it is digit
    lNumber = sR - '0'  // in most languages I know this will convert '1' char into 1 integer


P.S. of course I haven't measured anything, I do not even know vbscript, just wanted to give you an idea on what can be changed.  

P.P.S.: My second point doesn't take into account that there is a chance that VBScript interpreter will do such an optimization for you.