It seems that LWP::UserAgent only sends credentials in response to a 401. I think you could manually add the appropriate header to your requests in an request_preprepare or request_prepare handler maybe. In my opinion getting an error 500 for a non-existing resource is a bug on the server side, but maybe manually adding the header is a good workaround.

Note that some authentication schemes are challenge/response, so you can't necessarily create a valid authentification header in advance.