The function wp_inf_scroll_404 fires on the wp hook. wp() handles most redirects, except if a post is renamed, the old slug redirect happens on the following hook template_redirect. Tested on trunk (3.3).
The quick fix is simply to move the hook from wp to template_redirect, which allows both old_url redirects and infinite scroll to work.
The longer fix might be to take a look at handle_404 in /wp-includes/class-wp.php for a more consistent handling of 404s.
Either way, big fan of the plugin. Thanks for the hard work.