I have been receiving this error message lately on our local
SharePoint server. The SharePoint native back up application is
where we see the error message. It starts backing up and appears to
complete but when the search service back ups, it fails with the
error message below.

"The search service was denied access. Check that you have provided
an account in: http: Memphis-svr-
43:30094/sps/searchservicemanagement.aspx with the appropriate
access to \\memphi-svr-33\portal\server backups\December07\12_11-
TNIfopo1_serv-Memphis"

Server 43 is my Web Server, Server 33 is the SQL DB server
I use a seperate NT domain acct to handle services and where SP
needs one that is not tied to a user's acct. But the acct has not
changed and is not disabled, etc. This just started happening one
day while running the back up.