John Mueller of Google responded to a complaint that after the webmaster removed a 301 redirect, the old page that was being redirected came back in the search results. John wrote on Twitter that for the new redirected URL to show up, you need to (A) be patient and (B) be convincing. By convincing John means that you need to make sure the new URL has a lot of links to it and maybe you can add the rel=canonical to it as well.
Here is the exchange of Tweets:
The webmaster went on to say it is already 3 months since they did so. But 3 months may not be enough if there original URL still has way more signals (links) pointing to it even after a 301 redirect was in place. Once the redirect is removed, adding a rel=canonical probably is your best bet. Or if you can get 50% of those who linked to the original URL to change the link to the new URL, then you are on your way.
Forum discussion at Twitter.