The author speaks of the complexity in managing and coordinating processes in a distributed system. By designing a microservice, you trade simplicity of software design for increased operational complexities. There's a shift in terms of problem solving too--it migrates from the cross functional engineers to the DevOps and distributed systems engineers.
Don't get me wrong--I think microservices are brilliant and make reasoning about application design easier. But be prepared to bring in some heavy engineering talent to coordinate all the things. Until there are open source frameworks for handling the difficult bits, it might be unwise for a start-up to go the microservice route. Microservices are purposed for scale (since reasoning about traffic is easier with a simpler service and there predictable traffic patterns from a microservice's clients).
Edit :
In terms of the examples you mention, I you may have the wrong idea. Think about fulfilling a specific goal or class of functionality, and make that a microservice: email gateway microservice, user/session microservice(s), SMS gateway microservice, etc. Each is a component that responds to various request types (you really should use RPC instead of REST for deadlines, retries, cancellation, pooling, etc.), but they all sit within a single domain of purpose. The service could be stateless or not, but you try to make the requests idempotent to aid client reasoning.
To again cite your example, several services may use regex, but there might be only one authority on "normalized input" (eg. addresses, etc.). Or maybe there is a client lib for that.
This brings up another point. Services at the periphery (dependency graph-wise) are coordinated by interior services. That can get complicated...