I am thinking of a table containing for each category page title the cat_id it refers to. When updating a page, a query joining that table and the category table could retrieve A) the cat_id needed to update category_links B) possibly the cat_title to display the "proper" links at the bottom of the article.
To clarify a bit my point, I'm saying that when Category:A redirects to Category:B, articles belonging to A and B should point to the same cat_id