Here is another use case for a factory: Building an AST data structure in a compiler. There are nodes to represent Constants, Addition, FunctionCalls, etc and you have to build a tree structure, which represents a program.
Now consider the case, where you build the addition of two constants ("36 + 6"). Using constructors, it could like like: new Add(new Const("36"), new Const("6"));
Using a factory: f.newAdd(f.newConst("36"), f.newConst("6"))
The advantage of the factory is that it can optimize on the fly and return a Const("42") node instead of an Add.
I remember that at some point gcc -O 0 was doing exactly that and it is pretty irritating if you write a decompiler and want to test it. Fortunately clang does it properly.
You are also correct that it happens in other places too. Some people overuse it, though. They abstract out the construction of their objects for no reason at all. You already have a constructor -- usually there no need to have an object that contains all the constructors.