Q:

If not hook_init(), what can be used for cached pages?

I created a module to keep query_string laden links from a client site active (per client's request, background question here). 
This code works wonderfully when I'm logged in (as user 1); however, I have later found that hook_init() does not run on cached pages. 
Should I place this logic into another hook? Should I take a different approach to intercepting and mapping these legacy links? 
<?php    
/**
 * Extends hook_init()
 *
 * Intercepts vidID or PID and forwards to the page's proper Drupal node.
 *
 */

function module_init() {

    if (!menu_get_item($_GET['q'])) {

        $pid    = isset($_GET['PID']) ? $_GET['PID'] : FALSE;
        $vidID  = isset($_GET['vidID']) ? $_GET['vidID'] : FALSE;

        if ($pid) {
            // handler code
        }
        elseif ($vidID) {
            // handler code
        }
    }
}

A:

I think you are asking the wrong question.
If a page is cached, it means that it got generated and cached at some point. At this point, your code in module_init() did run. If your code generated a redirect (via drupal_goto()), this redirect will get cached.
There should not be anything wrong with this scenario, so maybe you should just clear the cache once?

A:

As it turns out, I did take a different approach. In trying to make use of other query string variables, I found it easier to use apache's mod_rewrite. That is, I used Apache's mod_rewrite to turn this /profile/?id=1234 into this /provile/id/1234. 
In turn, in Drupal, we added aliases of profile/id/1234 to the appropriate user profile. 
All turned out well. It's a much more managable solution. Old URLs are in tact. Result: everyone's happy.
.htaccess 
# Rewrite old URLS
RewriteCond %{QUERY_STRING} PID=([0-9a-zA-Z]*)
RewriteRule ^faculty/ /faculty/%1/? [R=301,L]

RewriteCond %{QUERY_STRING} vidID=([0-9]*)
RewriteRule ^videos/ /video/id/%1/? [R=301,L]

