I used to run a crontabbed script that queried a cgi-bin giving back the remote address
I use a very similar system (in PHP), activated by a wget request from /etc/ppp/ip-up.local (Linux). Another tactics I use occassionally when having to improvise is a remote syslog and a crontab entry that each 5 minutes spits a heartbeat message into the log (so each 5 minutes I get an UDP packet telling me the address on which the machine currently is; brute force, reliable, small overhead, abuse-resistant).
built-in this is now much more painless (no need to hack ddclient to parse your router's status page). More interesting, current wireless routers seem to support VPN tunnelling (IPsec, specifically). Given the capabilities, it would be a piece of cake to slip a VoIP package such as Speak Freely into it. With a headset/USB connection and a web interface to control the app it would certainly provide some added value and be immune to firewalling woes.
Works, proven experimentally. One fateful day my ISP cut off all UDP traffic above and including port 1024 (they reinstated it two days later, so I suppose it was a hasty defense against a DDoS attack). I had a VPN connection to my office LAN, so I opened the two UDP ports on the firewall and set up portforwarding in iptables, and after some wrestling caused by my relative inexperience I got it working. Was surprisingly reliable. By the way - thought a bit about the ringing and authentication. Why we have to unite the call request system with the rest of the IP phone application? Couldn't we use it as an entirely separate process, maybe something simple based on eg. SSL or HTTPS, employing client certificates? This way we reduce the modifications of the VoIP component itself to bare minimum or perhaps none at all. Maybe it could be as simple as a perl or PHP script on the listening side, and a script calling curl on the other side.