Assuming that in each case the "hostname" part you want to extract:
".*?_(.*?)_.*?" will do it for strings with the form "<something>_HostName_<anything>"
Zone_.+?_(.+?)_.*+ will catch "Zone_<something>_Hostname_<anything>"
In case you haven't seen it, a way to test your regexp it to use the GUI: from the "Automatic Host Resolution Regexp Wizard" window, once you've added an expression click on the "..." small button at the right of the "Regexp" line to access the "Regular Expression Editor" to test live your expression, it's handy to figure out what's the output.
There's also a link to an HTML help page with all regular-expression you can use.
Hope that helps.
/fx