Every morning, I receive a batch of old notifications. They are either ones I have cleared or ones I haven't seen yet (delayed). Some of them are for items I have downloaded previously, calendar notifications, and just about any other app I have on the phone which had notifications the day before.
Part of the problem is not receiving most notifications as they happen.
Since you tried the cheat cache partition trick, and it didn't work.... did you try the notification settings? It's found when toy pull down the notification shade and its on the bottom.