Here's post number two in the series from Jo Nesbo's The Leopard. In this extract, one character says "I know for certain of others with the selfsame reputation who categorically are not" (my emphasis).
The other chap tells him that using both the expressions for certain and categorically is a tautology. It's not, of course. They do mean the same thing (here, at least - categorically can also mean other things), but they don't refer to the same bit of the sentence. For certain applies to know, so Gjendem is certain about the state of his knowledge. Categorically applies to are not, i.e. to their state of being rather than to his knowledge. This doesn't mean that an editor might not suggest rewriting for stylistic reasons (after all, it means the same without either phrase), but it's not a tautology.