We experience a problem with creating custom redirects for old urls. If we update the URL key of a product the old URL stops working (404), although the checkbox "Create Custom Redirect for old URL" is checked (right below URL key). Its Magento ver. 18.104.22.168. Any clue what could cause the issue? I'm running out of ideas unfortunately. Thanks for any tip!
Please try re indexing after you make the change.
this can be done in cpanel or ssh to magento root and run:
php ./shell/indexer.php -reindexall
Also take a look into Catalog > URL rewrite management, there may be something odd going in there; for example one time I found one page that somehow had 10 URL rewrites and I was only able to get it to work after deleting them all. You could also try setting up a custom rewrite here to get this working.
Have a look at here for manually re-indexing: http://davemacaulay.com/manually-reindex-data-in-magento-using-ssh-command-line-ee-1-13/.