The comments about the service account not being sysadmins is most likely not your problem. Agent will refuse to even start if it isn't sysadmin. I.e., if the agent service is running, you know it is sysadmin. I just tried a couple of things (including making the Agent login a user in msdb and there being db_owner) to get Agent started without being sysadmin, and whatever I tried made the Agent service refuse to start.
But, by all means, check and double-check that Agent is indeed sysadmin. I can think of two, very unlikely IMO, cases where you do have Agent running as not a sysadmin:
- Agent has a combo of privileges high enough to start but not being sysadmin. As I noted above, being a user in msdb and there being db_owner isn't enough. So it has to be something really radical. Perhaps having CONTROL SERVER but not being sysadmin? Anyhow, not likely, at all.
- You removed sysadmin privileges while agent is running. And you didn't re-start it since. So, the checks made at startup passed since agent was sysadmin at that time. This assumes that you removed sysadmin from Agent and didn't re-start agent since that. IMO, not likely either, but plausible. I'm not sure how Agent reacts if this happens, but it sure isn't a supported config (obviously :-) ).
Btw, you don't need Profiler to trace. Use the modern trace engine instead: Extended Events. Here are my tips on how to get started with XE: http://sqlblog.karaszi.com/tips-for-getting-started-with-extended-events/
Now, trying to be productive:
I've seen similar error messages when the machine wasn't re-started since SQL Server was installed. The reason being that the OS PATH environment variable doesn't include the path to SQLCMD. This was at least 20 years ago, so memory it a bit hazy, but I have a distinct recollection of this. Back then SQLCMD was installed with the engine. Not, I think it is installed by client components (but I'm not sure), but you get where I'm getting at.
Also, I have some difficulties understanding below:
The problem is, if I turn off the worryingly generous 'public' select
permission and try to add the SQLServerAgent user (which is the user
the agent is running under and the user that owns the agent job) and
give them select permissions, the job fails with this error message:
Please be very clear with the distinction of logins and user. Are you saying that you created a user in your database for the login that agent is using and granting that user SELECT permission isn't enough? But what is weird is that you made that user the owner of the job!!? A user doesn't own a job. A job is owned by a login. This is why we need to super-clear with how we phrase security related things regarding the distinction between a user and a login. So perhaps you meant to say that you make the login that Agent is using the owner of the job? How about making sa the job owner? Agent need to be sysadmin (as I said earlier), so it isn't any difference from a security perspective who owns that job as long as it is a sysadmin. That is one troubleshooting measure to test.