First, keep in mind that vbs files aren't executable. If you are calling them from a batch script I'd recommend calling the interpreter directly so you can be 100% certain which one it will use, cscript.exe or wscript.exe.

To answer your actual question, I have started using hstart.exe to launch executables to ensure they request elevated permissions. I've had significantly more luck with this than about any other method I've tried.

www.ntwind.com/.../hstart.html

I in no way work for that company, but have used it to get powershell scripts to work among other many other things.