What would be the best way to expose certain functionality in a Dotnet VSTO Excel add-in to VBA, without requiring the user to be a local administrator (i.e. no COM registration, no HttpListener)? Would it be possible to use Microsoft Message Queues from VBA?
If I may interpret your question as broadly as "How do I expose functionality in a .Net assembly to Excel without COM registration" then an excellent solution is to use Excel's XLL interface. Basically one deploys an xll shim and an associated .Net dll. When the xll is loaded it reflects over the dll and exposes the functions therein to Excel.
An open source implementation can be found here http://exceldna.typepad.com/blog/2006/01/introducing_exc.html
A commercial, closed source, but more feature rich one here http://www.managedxll.com/