Ken IM'ed me just after he posted this to see if I happened to have run in to the same problem.  Ironically I have had a task in queue for a couple of weeks to build a public-facing WSS site for a side project I'm working on.  I got all the way through configuration and recalled I would need to configure the "Internet" name.  Here's how: 

Link to Ken Lince - Delta Force Partner Technology Team : Alternate Access Mappings for SharePoint 2007

This alone is a major improvement from previous versions of WSS.  The issue is with how name translation works when the site was built using one host name but needs to understand that it may have links called that include some totally other FQDN.