I have been searching for a solution for this problem on and off for the last half year. But each time I look, it seems impossible to do this with the SSH protocol.
The client does not send the hostname as part of the SSH protocol.
It might send the hostname as part of a DNS lookup, but that might be cached, and the path from client through resolvers to authoritative servers might not cross the proxy, and even if it did there is no robust way of associating specific lookups with specific DNS clients.
There is nothing fancy you can do with the SSH protocol itself either. You have to pick a server based without even having seen the SSH version banner from the client. You have to send a banner to the client, before it will send anything to the proxy. The banners from the servers could be different, and you have no chance of guessing, which one is the correct one to use.
Even though this banner is sent unencrypted, you cannot modify it. Every bit of that banner will be verified during connection setup, so you'd be causing a connection failure a bit down the line.
The conclusion to me is pretty clear, one has to change something on the client side in order to make this connectivity work.
Most of the workarounds are encapsulating the SSH traffic inside a different protocol. One could also imagine an addition to the SSH protocol itself, in which the version banner send by the client include the hostname. This can remain compatible with existing severs, since part of the banner is currently specified as a free form identification field, and though clients typically wait for the version banner from the server before sending their own, the protocol does permit the client to send their banner first.
However the solution that worked best for me was actually to use IPv6.
With IPv6 I can have a separate IP address assigned to each server, so the gateway can use the destination IP address to find out which server to send the packet to. The SSH clients might sometimes be running on networks where the only way to get an IPv6 address would be by using Teredo. Teredo is known to be unreliable, but only when the native IPv6 end of the connection is using a public Teredo relay. One can simply put a Teredo relay on the gateway, where you'd run the proxy. Miredo can be installed and configured as a relay in less than five minutes.