I finally got this all working. There were a couple of separate issues. Starting the queue manually was failing due to some of our own code in the job queue dispatcher. Once that was resolved I still couldn’t get a queue to start automatically though. I discovered through trial and error that in a multi-tenant environment the Services Default Company is not actually where you want to put the default company. Instead, you must specify a Default Company when you mount the tenant in addition to enabling NAS services for that tenant. You must do this even if there is only 1 company within that tenant. Also, the Windows account running the service must be a user within the tenant – even if you aren’t using Windows Authentication for that service.
Now that it’s all set up though it works well – I can have 1 NAS service instance with all of the tenants mounted to it each with their own job queue, entries, and recurrences.