This doesn't really answer your question, but at the point where you want the server to exist on the network without DHCP, and you're giving it a static IP from DHCP anyway, it seems like you're not gaining a lot with DHCP. I would just give it the same static IP manually that would otherwise come from DHCP. That way you know what IP its on, and you can use that static IP through a direct link just as well as you could a link-local (APIPA) address.
If you don't know the IP then your problem becomes one of network discovery, and a portmap is probably the easiest way. The link-local subnet size is most of a /16 subnet, which means you've the better part of 2^16 hosts to scan (another benefit of choosing a smaller local subnet and configuring statically, rather than using the RFC-defined link-local subnet, is having a lot less hosts to scan). A good portmap utility ( nmap being my favorite) will be able to scan a given port on an entire range of addresses. Unfortunately you may need to run a few different scans to cover the rather arbitrarily (and inconveniently!) defined link-local range 169.254.1.0 - 169.254.254.255, which can't be defined as a CIDR bitmask subnet, as it's 168.254/16 "minus" 169.254.0/24 "minus" 169.254.255.0/24, but you could do something like this in a bash shell:
for i in `seq 1 254`; do
nmap -p 3389 169.254.$i.0/24;
done > rdp-listens.txt 2>&1
Since that's going to generate a lot of output, I redirected it to a file to peruse after its done. But that's quite a lot of effort, compared to just giving it one static IP on your network and writing it on a post-it note which is stuck to the box :).
There are some other options, including those mentioned by others, but they're not as sure of a slam dunk. Briefly:
Pinging it by computer name might work, if you know the computer name. Unless we're talking about DNS (and though it's possible, most DNS/DHCP configs don't configure DNS A or PTR records between client-supplied hostnames and DHCP-supplied IPS) that would be a windows computer name, and I don't know how the resolution would work exactly.
I'm skeptical about wire sniffing. Wireshark or similar would require actually seeing RDP traffic for this host, to be able to help you determine it's IP. There are a few problems with that. First, unless this is a network sharing a collision domain ( wireless, or a Hub-connected network ), you're never going to see those packets. Given the scenario I'm guessing you're not using wifi, and you'd be about the only person left in the world running a wired network on a Hub, so you probably have a switched ethernet, which means you'd never see that traffic. ( Some fancier switches allow this kind of thing, but since your root problem here is "I'm worried I won't know the IP", I'm guessing this isn't enterprise level). So there's unlikely to be an easy way to sniff this information off the network. Secondly, this would require traffic to be on the network already - given the scenario, I'm guessing there won't be RDP traffic in the scenario where you don't know the IP address, and if there is, you can just ask your compatriots what its IP is :)
One final approach I can think of might be ARP. You should be able to ARP the network address given the MAC address of the network interface. However, I'm not sure the IP in question would necessarily be in the ARP tables.
Hope it helps!
http://en.wikipedia.org/wiki/Link-local_address
http://en.wikipedia.org/wiki/Classful_network