This super helpful error message and some Googling led to a solution. I really did not believe it when I found it. But some days are like that.

Severity    Code    Description    Project    File    Line    Suppression State
Error        Web deployment task failed. ((6/29/2016 10:07:24 AM) An error occurred when the request was processed on the remote computer.)

(6/29/2016 10:07:24 AM) An error occurred when the request was processed on the remote computer. Unable to perform the operation. Please contact your server administrator to check authorization and delegation settings.

And the winning blog post (certainly not MS docs) goes to A Software Guy’s Blog (Eric Kelm).

Summary
When you add Microsoft Web Deploy to an IIS server, the install adds two local user accounts, both with an expiring password. So 90 days, or whatever your expiration policy is, after you install, web deployment just stops working. The trick is to modify both accounts to check “password never expires”.

Thanks, Eric. And thanks, Microsoft. Eric’s post is four years old and this problem still exists. Epic fail.