How can I delete Hotmail emails when using the Gmail app on my phone
What do you know... Shortly after posting this, I found a thread in the Gmail help forum with a solution that worked for me, by user Nico P.

Quoting here, for reference:


  If you look at your folders from your outlook account you'll notice
  that there is a folder named "Trash" (or another equivalent) and
  another folder that is the actual folder for deleted emails. 
  
  Try to delete this "Trash" folder , it will move it to the actual
  trash folder (you can then safely deletethis "Trash" folder from here)
  and sync your Gmail app again. You'll notice that the "Trash" folder
  is now gone. 
  
  Then retry to delete an email. It should work and appear in the
  "deleted elements" folder.
  
  I think Gmail is programmed to automatically identify the trash folder
  and when this "Trash" folder is present it's messing up with the real
  delete action as the "Trash" folder is actually an artefact and not
  the real one.
  
  Hope it helps, this solution solved my deletion problem.


Note that you don't need to delete the Trash folder. You could just rename it to get the same effect.