It's as if there is some kind of broadcast packet needed for the IDE to recognize the Yun that isn't being passed by my WiFi access point. I would assume that this would also be a problem going over the Internet.
Indeed that's what happens: a broadcast message is sent by the yun on all the networks it's attached to. It's called zeroconf
although the name Bonjour (the Apple implementation) is more known
In fact, I don't understand why arduino yun has the functionality of uploading sketches over wifi and it hasn't got the functionality of uploading over the internet. At the end of the day it is only to search for the ip address and stablish a connection as a private network.
If you can manage to access yun's webpanel from outside, and if you're running the latest version of openwrt-yun, you can upload a precompiled sketch via web.
Locate and save the compiled .hex file, go the yun's webpanel, scroll down until you find the upload button, select the .hex file and upload it.
If you wish to do that via IDE, please consider contributing to the Arduino IDE project