Performance, namespace pollution etc are all secondary in my view. Ask yourself what is logical. Is the method logically operating on an instance of the type, or is it related to the type itself? If it’s the latter, make it a static method. Only move it into a utility class if it’s related to a type which isn’t under your control.
Sometimes there are methods which logically act on an instance but don’t happen to use any of the instance’s state yet. For instance, if you were building a file system and you’d got the concept of a directory, but you hadn’t implemented it yet, you could write a property returning the kind of the file system object, and it would always be just “file” – but it’s logically related to the instance, and so should be an instance method. This is also important if you want to make the method virtual – your particular implementation may need no state, but derived classes might. (For instance, asking a collection whether or not it’s read-only – you may not have implemented a read-only form of that collection yet, but it’s clearly a property of the collection itself, not the type.)