I ran into a scenario recently whereby installing Web Deploy didn't create the WDeployAdmin and WDeployConfigWriter users. After attempting to uninstall/reinstall a few times, to no avail, I ended up configuring the users manually. Here's how I did it:

  1. Create local users WDeployAdmin and WDeployConfigWriter. Since you won't need the passwords after this process, I recommend using a complex password (like via  strongpasswordgenerator.com)
  2. Disable password expiration on both accounts to avoid issues in a few months time
  3. Add WDeployAdmin to the local Administrators group
  4. Open %windir%\system32\inetsrv\config in explorer and grant WDeployConfigWriter write permissions to it (ignore the permission denied error on config/schema)
  5. Open IIS and select "Management Service Delegation", which is at the server level (not on a site)
  6. For each item with WDeploy* in the User Name column:
    1. Select the row and click "Edit" (or double click)
    2. Click "Set" next to "Identity"
    3. Re-enter whichever user was set as well as the password you generated earlier
    4. Click OK

Everything should be fine after that. If deploys are still failing, check out the "Web Deploy" event log.