I was deploying a new Cisco 1921 router and couldn’t get an internet connection going. I did a Show IP route and saw no routes (not even my static) and got the message “ICMP redirect cache is empty”. After double checking that IP routing was enabled (it was), I rebooted but had the same issue. I did a “debug ip routing static” and then removed and re-added my static route. I then got an error dealing with the routing database.
In the end I turn off routing with a “No IP routing” and then turned it right back on with “IP Routing” and that immediately resolved the issue. It was very weird though.