Because I can never remember, here's how I did it.
In the file /usr/share/zsh/4.0.4/functions/_host, I removed the line:
hosts=( "$_cache_hosts[@]" )
And added:
hosts=( `perl -pe 's/(.*?)[, ].*/$1 /;' ~/.ssh/known_hosts2 ~/.ssh/known_hosts | egrep -v '^[0-9]' | sort | uniq` )
This allows you to tab complete to all of the hosts in ~/.ssh/known_hosts* - ie, any host that you have ever ssh'ed to before. Ssh'ing to a new host makes it get added to that list, so that it will then be in your tab completion list automagically - nothing to update.
By default, completion is to your /etc/hosts file, which seems moderately useless to me.