I am not much on networks, but could you use a ping script to locate it? This is what I tried for my network address. Depending on you network, 20 is enough for me, you could also use a shell script to loop through the ip addresses get hostnames, ssh 192.168.0.3 hostname.
pi@RPi3:~ $ time for x in $(seq 2 20); do ping -rc1 -W1 192.168.0.$x | grep 'from'; done
64 bytes from 192.168.0.2: icmp_seq=1 ttl=64 time=1.31 ms
64 bytes from 192.168.0.3: icmp_seq=1 ttl=64 time=6.20 ms
64 bytes from 192.168.0.4: icmp_seq=1 ttl=64 time=1.53 ms
64 bytes from 192.168.0.5: icmp_seq=1 ttl=64 time=0.104 ms
64 bytes from 192.168.0.6: icmp_seq=1 ttl=64 time=5.69 ms
64 bytes from 192.168.0.7: icmp_seq=1 ttl=64 time=5.36 ms
64 bytes from 192.168.0.8: icmp_seq=1 ttl=64 time=1.20 ms
64 bytes from 192.168.0.9: icmp_seq=1 ttl=64 time=2.38 ms
64 bytes from 192.168.0.12: icmp_seq=1 ttl=128 time=4.57 ms
64 bytes from 192.168.0.13: icmp_seq=1 ttl=64 time=54.7 ms
64 bytes from 192.168.0.15: icmp_seq=1 ttl=64 time=6.31 ms
64 bytes from 192.168.0.16: icmp_seq=1 ttl=128 time=1.41 ms
real 0m7.292s
Run arp -a -n | grep -v 'incomplete' to get the MAC address.
...
? (192.168.0.3) at 00:21:2f:38:9a:9f [ether] on wlan0
...
Now you can ssh pi@$(arp -a -n | grep '00:21:2f:38:9a:9f' | awk '{print $2}' | tr -d '()'). Reference https://askubuntu.com/questions/643928/is-it-possible-to-connect-remote-machine-using-mac-address.
On a Class B network the following script will find the IP addresses. It runs in background and takes about 5 to 10 minutes to run, you have to press [Enter] to get prompt back.
for x in $(seq 1 255); do
(for y in $(seq 1 254); do
ping -c1 -W1 -I eth0 169.254.$y.$x 2> /dev/null |\
grep 'bytes from'
done &)
done