Why would ssh fail to expand %h variable in .ssh/config?

You are using OpenSSH 5.3; %h was only introduced in OpenSSH 5.6:

Changes since OpenSSH 5.5
=========================

 * Expand %h to the hostname in ssh_config Hostname options. While this
   sounds useless, it is actually handy for working with unqualified
   hostnames:

     Host *.*
        Hostname %h
     Host *
        Hostname %h.example.org

man ssh_config does not mention that %h will be expanded in HostName clause. I'm using openssh5.9p1

edit: it did and I missed it

If setting up some proxy server ( a local-only one will do ) won't bother you, maybe some workaround with ProxyCommand is possible.

Or, you can enumerate a few hostnames in .ssh/config .