The man page says:
Indicates that the rules used in validating addresses supplied in a bind(2) call should allow reuse of local addresses. For AF_INET sockets this means that a socket may bind, except when there is an active listening socket bound to the address. When the listening socket is bound to INADDR_ANY with a specific port then it is not possible to bind to this port for any local address. Argument is an integer boolean flag.
I relied on "For AF_INET sockets this means that a socket may bind, except when there is an active listening socket bound to the address.", and I reckon so did #2850 (closed). This is, however, misleading: it's only true when a port is specified. When no port is specified, a port is selected from those with no connections at all, not those without a listening socket. https://blog.cloudflare.com/how-to-stop-running-out-of-ephemeral-ports-and-start-to-love-long-lived-connections/ has a good explanation of this. According to the article, the Linux-specific solution is to set IP_BIND_ADDRESS_NO_PORT. I think it's probably not so terrible if it's Linux-specific, since this only affects relay operators using OutboundBindAddress. AIUI, there are a few reasons why this flag isn't set by default: the main reason is that getsockname won't work between bind and connect for sockets using this flag; another reason is that this adds the possibility that bind could succeed but connect fails. Neither apply to tor, the former because tor doesn't use getsockname in this manner, and the second because tor already handles the case where connect fails due to EADDRINUSE because OutboundBindAddress is optional.
@adietrich if you could test this, I would greatly appreciate it.
IP_BIND_ADDRESS_NO_PORT is supported back to Linux 4.2, so unless you're running centos 7 or debian 8 it should solve your issue. thanks!