There are plenty of examples where you want to use an abstraction over various immutable record types. Services vs. records is a false dichotomy and there is power in mixing the two.
Yes, there are lots of functions that don't make sense to co-locate with their operands. Static classes are fine for those functions if both of these are true: the function requires no dependencies, and there is only one reasonable implementation of the function. In practice I find it rare that both of these are true. With a good Dependecy Injection system (and bad ones abound), requesting a service instance is just as simple as referencing a static class.
> there is only one reasonable implementation of the function
this. In the absence of polymorphism, a static function is just fine. I am in the phase of avoiding object notation in preference of functional notation whenever possible. I leave OO notation to cases where, for example, there is polymorphism as the functional wrapper will add little to no value.
Types are just a layer on top of your code that help enforce certain logical / mathematical properties of your code; those that your particular type system enables you to constrain.
Most actual type systems are not powerful enough to allow you to fully specify the logical objects you are actually working with, but thinking about exactly what they are and how to constrain them as well as you practically can (or should) is in my experience one of the important skills of an advanced programmer.
By the way, if you know what I mean and have found a good way to effectively teach this way of thinking, let me know, because I have often been unsuccessful. I see people left and right thinking about code as a procedure that will with trial and error ultimately be made to work, rather than as an implementation of logical / mathematical objects that can be correct or not.