【追記】「Script Control」は64bit版Officeでは基本的に利用不可なので現在ではこの技を使うことはできません
「Script Control」を使うのがポイント
さらに「encodeURLを呼べる関数を作成する」のもポイント
Dim objSC As Object 'Script Control
Dim s As String
Dim strFunc As String '関数文字列
Set objSC = CreateObject("ScriptControl")
objSC.Language = "JScript"
strFunc = "function encode(s) { return encodeURI(' + s + '); }"
objSC.AddCode strFunc
s = objSC.CodeObject.encodeURI("テスト")
Debug.Print s