HTTP is an application protocol; it's application domain is the transfer of documents over a network. The HTTP specification describes the semantics of the request messages and responses that are used by participants in that protocol.
So a REST API is a facade - we're taking some service that knows how to perform useful work, and disguising it as an HTTP compliant document store. All the useful bits are side effects, performed in response to messages that describe the manipulation of documents.
See Jim Webber: Domain Driven Design for RESTful Systems.
Your reference implementation of REST is the World Wide Web; HTML does everything by GET and POST. All of your domain protocols are variations of "start here, follow these links, discover this form, fill in the details and submit". It's perfectly reasonable to have a protocol that submits a form to say "please delete/tombstone/archive this record in your data store".
It's just like writing somebody a note that says "please throw your apple in the trash". We deliver a document (the note); the apple going into the trash is a side effect, we get a note back describing what happened (or didn't happen, if there was a problem).
Furthermore, DELETE is something of an odd bird...
The DELETE method requests that the origin server remove the association between the target resource and its current functionality. In effect, this method is similar to the rm command in UNIX: it expresses a deletion operation on the URI mapping of the origin server rather than an expectation that the previously associated information be deleted.
Relatively few resources allow the DELETE method -- its primary use is for remote authoring environments, where the user has some direction regarding its effect.
If you imagine the document store as some map of Key-Value pairs, the
DELETE semantics say "remove the key from the map", not "remove the key from the map AND garbage collect the value".
The server might actually delete the value; but it could instead add a tombstone, or null out the data, or leave the data as is but discard the cryptographic key used to decode it, or even just leave the value, knowing that it is no longer reachable via that target-uri... there are lots of different ways to implement a behavior that matches the semantics.
The critical insight is that the HTTP specification doesn't say what you have to do, but rather describes what generic participants (like an HTTP aware cache) are allowed to assume about the requests and responses that they see.
One other argument was that when user requests deletion, Service A can just use the POST API provided by Service B to write "an empty resource".
So the main arguments about what is going on here listed by Roy Fielding: REST APIs must be hypertext driven
REST doesn’t eliminate the need for a clue. What REST does is concentrate that need for prior knowledge into readily standardizable forms.
What makes the web work is that we all share in common a bunch of standards, and protocols for creating new standards, so that everybody can agree what
DELETE means, and what
PATCH means, and how to process
application/problem+json, and so on.
In your situation, where the same team controls both service-A and service-B? The costs of unstandardized out of band information are (at least in the short term) very low. An RPC "just read the docs" approach may suffice to get the job done.
Another consideration might be the reliability of the network between these two services. DELETE promises idempotent semantics that aren't promised by POST, which may make your life easier when messages are lost due to unreliable transport.