Not sure how difficult this is, if it's harder then it seems let me know.
It's not
that difficult to script this in VBS, my limited VBS/VBA knowledge and some Googling was enough

.
But since you want an VBS-script it will remain very limited as far as I know. Because it only works with a folder with
only bitmaps (*.bmp) with a size in pixels which
exactly match your screen dimensions.
Anyway, here's the script (tested in WinXP):
Formatted for
Visual Basic with the GeSHI Syntax Highlighter [
copy or print]
' WallpaperChanger.vbs - by Winkie - Last changed: 20100927
Option Explicit
Dim oShell, oScripting, aFilesArray
Dim sWallpaperDir, sFolder, sFile
Dim i , iFiles, iSelection
sFolder = "E:\Test\" ' Include quotes and last backslash
Set oShell = CreateObject("WScript.Shell")
Set oScripting = CreateObject("Scripting.FileSystemObject")
Set sFolder = oScripting.GetFolder(sFolder)
iFiles = CInt(sFolder.Files.Count)
ReDim aFilesArray(0)
For Each sFile in sFolder.Files
ReDim Preserve aFilesArray(UBound(aFilesArray) + 1)
aFilesArray(UBound(aFilesArray)) = sFile.ShortPath
Next
i = 1
Randomize
iSelection = Int((UBound(aFilesArray) - i + 1) * Rnd + i)
oShell.RegWrite "HKCU\Control Panel\Desktop\Wallpaper", aFilesArray(iSelection)
oShell.Run "%windir%\System32\RUNDLL32.EXE user32.dll,UpdatePerUserSystemParameters", 1, False
If it doesn't necessarily have to be an VBS-script, I'm sure an AutoHotkey-script can solve the limitations.
HTH,
Greetings Winkie