I use the sledgehammer approach and search/replace from template_process_html:
function foo_process_html (&$variables)
{
$variables["page"] = str_replace("http://internal.example.com/", "/", $variables["page"]);
}
You can also get fancy and use preg_replace
if you need better control. I typically end up needing this when I move a site from our staging server, which is a subdomain off of ours, onto a client's own domain.
If I were in your shoes, I would think about having an internal theme and an external theme, combined with one of the choose-a-theme-based-on-domain-name solutions. Then you can add preprocess/process as needed to just the external theme.