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? 

&lt;?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
        }
    }
}
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?