I am trying to figure out if I should fight against this policy.
Change your organization, or change your organization.
The policy sounds very wrong, in a general context. It may make sense under the circumstances. I would never advocate those practices in a system being built from scratch, but it might be a practical solution given the local constraints.
Fielding wrote in 2008
REST is intended for long-lived network-based applications that span multiple organizations. If you don’t see a need for the constraints, then don’t use them.
REST was designed for building web-scale applications; for example, the world wide web. An important part of that design was paying attention to generic components, and what they could know about the messages being passed. The HTTP Headers are effectively meta data so that generic components know what is going on. This in turn affords various optimizations like caching.
Which is to say, if you don't put the authentication information into message where the generic components expect, then they aren't going to see that information, and they aren't going to react appropriately.
See RFC 7234, Storing Responses to Authenticated Requests.
Now, that argument in particular is somewhat weaker than it was twenty years ago, because we're likely to be using an encrypted connection to exchange the messages. Under those circumstances, the capabilities of the intermediaries are less of a concern, because they shouldn't be able to read the messages anyway.
For POST and PUT methods, the auth string was accepted in the message body. For GET and DELETE methods, it was in the URL query. This seems wrong to me, but I can't exactly explain why.
Strictly speaking, embedding authentication data in the payload of a PUT request is semantically incorrect
The PUT method requests that the state of the target resource be created or replaced with the state defined by the representation enclosed in the request message payload.
Unless the goal is to include the authentication information in the updated representation of the resource, it doesn't belong there.
Putting authentication credentials into the query part of the URI in the request is "wrong" because the URI is an identifier - /foo/bar?user=alice
is a different resource than /foo/bar?user=bob
. The fact that these two resources always have the same representation, and that deleting one necessarily deletes the other, is an implementation detail that isn't visible outside of the server.
What it sounds like to me is that your team is not trying to do REST, but are instead implementing an RPC protocol using HTTP as transport for messages. Which is fine if they don't need the scaling properties protected by the REST architectural style.
Is there a valid alternative to HTTP headers for sending auth credentials
Client certificates would be another approach; which is to say, the client and server negotiate an encrypted connection, and the server knows who the client is because the responses provided by the client are consistent with the client's known public key (which implies that the client has access to the private key).
(There's not really anything wrong with putting authentication credentials into the POST body. POST is so generic it really doesn't matter; intermediary components aren't allowed to draw many conclusions when the semantics are so loosely specified. It's kind of clumsy, though -- imagine a web page where every link was replaced with a form.)