When did this start?
Do you have any metas like og:title? If so, do they happen to be different than the actual title tag (whether or not they have any remnants of the old name/URL)?
I work on a pretty large site, and starting on Sept 15th or so at the latest (could be a couple of days before but hard to know for sure), Google has been using the page's H1 tag for the title - instead of the actual, and better, title tag - a conditionally modified version of the H1 tag. After that weekend, impressions were up, rankings didn't go up or down more than the normal fluctuation of +/- 0.5-1.5, but CTR tanked. I'm curious if your title tag woes started at the same time - maybe it means something, maybe it doesn't.
I had a different site a few years ago that once had something more similar to your issue - Google was actually appending the company name to the end of the supplied title tag on a small, but still significant number of pages that used to have them, but like yours, it was a while ago and the new ones had been showing in the SERPs just fine until then. I don't remember how long it took to resolve, but it wasn't more than a few weeks. The suggestions given here are good ones, but I think it'll eventually resolve on its own, too.