"Deja vu all over again" is an example of either a semi-literate (when the speaker does not know what deja vu means) or a jocular use (when the speaker tries to be funny).
Can you give similar examples of (possibly double) usage?
English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. It only takes a minute to sign up.Sign up to join this community
Actually, there's nothing wrong with the phrase (I get deja vus on monthly basis), but I see what you mean. I vaguely recall the original sentence went something like "It was another deja vu all over again".
Getting back to your original question - I've always loved how you can fall down in English. Like you could fall up.
There's some nice examples of tautology in formal use, eg. terms and conditions, null and void. I seem to have heard somebody argue that the whether... or... structure also follows the above, tautological suit, as it's enough to say whether.