I have been reading that creating dependencies by using static classes/singletons in code, is bad form, and creates problems ie. tight coupling, and unit testing.
I have a situation where I have a group of url parsing methods that have no state associated with them, and perform operations using only the input arguments of the method. I am sure you are familiar with this kind of method.
In the past I would have proceeded to create a class and add these methods and call them directly from my code eg.
From a theoretical design standpoint, I feel that Utility classes are something to be avoided when possible. They basically are no different than static classes (although slightly nicer, since they have no state).
From a practical standpoint, however, I do create these, and encourage their use when appropriate. Trying to avoid utility classes is often cumbersome, and leads to less maintainable code. However, I do try to encourage my developers to avoid these in public APIs when possible.
For example, in your case, I feel that UrlParser.ParseUrl(...) is probably better handled as a class. Look at System.Uri in the BCL - this handles a clean, easy to use interface for Uniform Resource Indentifiers, that works well, and maintains the actual state. I prefer this approach to a utility method that works on strings, and forcing the user to pass around a string, remember to validate it, etc.