That assumes running emacs locally, what is being discussed is if you
    are running Emacs remotley, i.e. over a remote X11 connection (e.g,
    ssh -X).

   Oh, sorry, my bad. I'm surprised to discover that it's apparently the remote
   application's job to ensure that it has a proper title when run remotely...

Not sure how it could work other wise, who would be setting the title
if not the program it self?  If it is remote or not isn't really
important here.

I'd assume that the program could give a frame name regardless, and someone 
on the local host (maybe ssh?) would use it to make a valid window name on the 
local host, e.g. transform "title" into "title on host". 

But I'm obviously not very familiar with how display servers work, so I trust that if it 
works this way, then there is good reason for it.
 

   For ssh connections at least, I guess that emacs could check if a ssh variable
   such as SSH_CONNECTION is set in the environment. But I'm not sure how
   robust it would be.

That would only work for SSH I think e.g., does GNU lsh set
SSH_CONNECTION?  What about telnet and Kerberos?  Are there other
ways, or protocols to do X11 forwarding?

I'd expect that most other protocols would be identifiable through such a setting, 
and that emacs would have to loop through all known such tests. 

As a bonus, it would also allow to make titles like "title on host [ssh]".