If I was sending these over to the server one at a time, I'd use DELETE, PUT or POST depending on the nature of the operation, but since I'm sending over a batch potentially containing all three types of requests, I'm not sure which method is most appropriate (aside from DELETE).
Which is the correct HTTP Method to use in this instance?
"It depends".
The key point is this: http semantics apply to resources, which live in the integration domain. The fact that these representations you are sending impact the domain model in interesting ways isn't relevant.
The method you choose should have unsafe semantics, since you are encouraging the origin server to change. You also need a method where the message body is meaningful. Of the methods defined within the HTTP spec, you have PUT and POST -- either of these is fine. PATCH may also be suitable, depending on whether or not you can make this collection of changes atomically.
Example: suppose what we are really doing is taking the body of the message, and sticking it into a queue to be handled "later". The REST part is taking that implementation, and dressing it up with an HTTP disguise.
Either PUT or POST is perfectly fine for that. Using POST to add something to a queue should not be a big surprise. PUT is analogous to inserting the message into a key value store.
HTTP is an application protocol whose application domain is "the transfer of documents over a network." -- Jim Webber
What you have at your client is a document, which happens to describe changes that you want to make in your domain model. You are using HTTP to transmit a copy of that document to the server. Does POST work for that? Yes. Does PUT work for that? also yes.
Consider this resource, which means exactly what it says on the tin
/newest-message-in-queue
Can you update that resource by sending a new representation via POST? Sure. Can you update that resource by sending a PUT? Of course. Will the side effects on the domain objects work either way? Yes.
Can the client tell the difference between this, and changing a value in a key value store? No <-- and that's the point; we're disguising our implementation behind a generic document store semantics, so that we can take advantage of off-the-shelf-ware.