Making them static is costly. If a method is static, then by necessity, the exact name of the class it appears in is scattered all over your application. If you someday decide that method needs to be polymorphic, or if you want to use a different implementation on certain platforms, or for debugging, etc, then you have to change code all over the place. If the method is non-static, though, then the name of the class can be much more localized, and the changes are easier to make. This is especially true if (as is always a good idea!) your functionality is represented by interfaces your service classes implement, and their clients are written to the interfaces instead of to the concrete classes themselves.
If you don't know what I'm talking about, our "OO,
Patterns, UML, and Refactoring" forum is a good place to ask!