It's not exactly "normal" but it certainly isn't rare. The cached documents that Google links ffrom the SERPs are not necessarily the same as the version used for generating the rankings. I've often seen rankings that were based on a fresher version than the displayed cached date.
And now from the above report, it sounds like the issue of version control is even more complicated and crossed-up than ever.
danijelzi - does that URL (removed 15 days ago) respond with a real 404 or 410 status? Or is the http status really 200 OK with just a 404 text message displayed on the page?