Factory Creation Methods Always Static?

I don't believe there is such a thing as a "strict definition" of a pattern. By their nature patterns exist to capture the essence of a problem which crops up time and time again in software and outline how a solution might look.

Specifically with the Factory pattern, no, there is no requirement that the factory methods be static. The essence of the pattern is that you have one object which is responsible for creating instances of another class. How you do this is really up to you, although a common way, as described in the pattern, is to use a static method on a class. However, we have a factory mechanism in one of our systems which is actually two-stage. You use a static method on a class to create the factory object, which can be configured to choose amongst a set of implementations, and then use the factory object to stamp out instances of the object that you need to do the real work.

Also consider the implementation of the factory pattern in a language which does not have static methods. For example, in Scala you would use an object instead of a class. Although the behaviour of this is a lot like using static methods on a class in Java, the nature of the implementation is quite different.

It depends on your needs. I generally prefer a static method for creation:

SpaceShip spaceShip = SpaceShipFactory.create();

Also, Java uses static methods for Factories in most cases.

Calendar calendar = Calendar.getInstance();

But if we're gonna create multiple instances from the same factory. Maybe we can prefer non-static way for it. We need some stateful fields as the Algorithm for this purpose.

SSHKeyFactory factory = new SshKeyFactory(Algorithm.RSA);
Key client1Key = factory.createKey();
Key client2Key = factory.createKey();
...

No, factories can hold state. It depends on what is needed.

I'd suggest that making is static seems good choice in the first instance - hovewer the moment you try to unittest statics you tend to run into problems.

Steer away until you specifically need them.

No, factory class by default shouldn't be static. Actually, static classes are not welcomed in OOP world since they can also convey some state and therefore introduce global application state. If you need only one factory object to be present, you can control it's creation through singleton pattern.

In case of factory method - it is ok to keep it static (actually there's no other reasonable way to go :)).