Redirection from observer not working (Fullpage Cache + APC turned on)

Question

I am trying to redirect to custom url if certain url is matched using event: controller_action_predispatch

a> Registering event: controller_action_predispatch

<frontend>
    <events>
        <controller_action_predispatch>
            <observers>
                <redirect_controller_action_predispatch>
                    <class>redirect/observer</class>
                    <method>controllerActionPredispatch</method>
                </redirect_controller_action_predispatch>
            </observers>
        </controller_action_predispatch>
    </events>
</frontend>

b> Implementing the observer model

<?php
class MagePsycho_Redirect_Model_Observer
{
    public function controllerActionPredispatch(Varien_Event_Observer $observer)
    {
        $action         = $observer->getControllerAction();
        $request        = $action->getRequest();
        $requestUrl     = isset($_SERVER['REQUEST_URI']) ? $_SERVER['REQUEST_URI'] : $request->getRequestUri();

        if (stripos($requestUrl, '/' . 'old-404-url-key') !== false) {
            $redirectUrl = Mage::getUrl('new-url-key');
            Mage::log('redirect-matched::' . $redirectUrl);
            $action->getResponse()->setRedirect($redirectUrl, 301);
            $action->getRequest()->setDispatched(true);
            return;
        }
    }
}

Above code works fine in localhost but not on live server where Full Page Cache + APC caching is turned on (Magento EE 1.13).

What am I missing, anything needs to be checked in case of Full Page Cache + APC turned on?

Any help is appreciated.

[EDIT]
The redirection issue is only for 404 error. If i try to redirect some non existing page (i.e. 404 page) to some valid page, the redirection doesn't work.