Have you checked URLs individually, particularly the old urls that are still showing in serps?
Assuming you're talking about competitive serps, it's somewhere between extremely unlikely and impossible that they would rank on their old urls for competitive searches if a header checker shows that these urls have been 301ed, unless Google has decided to show redirected urls it feels might be in some way suspicious or odd.
I am talking about widget reservation site for major destinations. Is that competitive enough? Yes, I checked the URLs separately, Google shows www.website.com/oldurl with _Anchor text - website.com_ title, and when I click, I am instantly redirected to www.website.com/newurl.
What was the query that returned in the above result. Was it perhaps this....?
No, the queries I use are those that I try to rank for, i.e. [destination widgets], [widgets in destination] in my case.
IMO, and this is a total guess... it would make sense only if the redirects were the problem.
If the inbound links to the redirected urls were the problem, then you wouldn't really be changing what's causing the trouble. I'm thinking after all this time, it doesn't make sense to go back to the old urls.
I'd check quality of inbound links and also really have someone knowledgeable check over those redirects.
I will have an eye of someone properly technical tomorrow and they'll look into it. The links to the old URLs were not of high quality (most of them come from 2004-5 link swap mania) and we did not really build any links in the last 3-5 years. New URLs may have acquired just a handful of links each as the vertical is highly commercial (i.e. few people link out).