There's one tiny difference between Java and C# that is relevant here. In Java, every member is virtual by default. In C#, every member is sealed by default - except for interface members.
The assumptions that go with this influence the guideline - in Java, every public type should be considered non-final, in accordance with Liskov' Substitution Principle . If you only have one implementation, you'll name the class
Parser; if you find that you need multiple implementations, you'll just change the class to an interface with the same name, and rename the concrete implementation to something descriptive.
In C#, the main assumption is that when you get a class (name doesn't start with
I), that's the class you want. Mind you, this is nowhere near 100% accurate - a typical counter-example would be classes like
Stream (which really should have been an interface, or a couple of interfaces), and everyone has their own guidelines and backgrounds from other languages. There's also other exceptions like the fairly widely used
Base suffix to denote an abstract class - just like with an interface, you know the type is supposed to be polymorphic.
There's also a nice usability feature in leaving the non-I-prefixed name for functionality that relates to that interface without having to resort to making the interface an abstract class (which would hurt due to the lack of class multiple-inheritance in C#). This was popularised by LINQ, which uses
IEnumerable<T> as the interface, and
Enumerable as a repository of methods that apply to that interface. This is unnecessary in Java, where interfaces can contain method implementations as well.
I prefix is widely used in the C# world, and by extension, the .NET world (since by far most of .NET code is written in C#, it makes sense to follow C# guidelines for most of the public interfaces). This means you will almost certainly be working with libraries and code that follows this notation, and it makes sense to adopt the tradition to prevent unnecessary confusion - it's not like omitting the prefix will make your code any better :)
I assume that Uncle Bob's reasoning was something like this:
IBanana is the abstract notion of banana. If there can be any implementing class that would have no better name than
Banana, the abstraction is entirely meaningless, and you should drop the interface and just use a class. If there is a better name (say,
AppleBanana), there's no reason not to use
Banana as the name of the interface. Therefore, using the
I prefix signifies that you have a useless abstraction, which makes the code harder to understand with no benefit. And since strict OOP will have you always code against interfaces, the only place where you wouldn't see the
I prefix on a type would be on a constructor - quite pointless noise.
If you apply this to your sample
IParser interface, you can clearly see that the abstraction is entirely in the "meaningless" territory. Either there's something specific about a concrete implementation of a parser (e.g.
XmlParser, ...), or you should just use a class. There's no such thing as "default implementation" (though in some environments, this does indeed make sense - notably, COM), either there's a specific implementation, or you want an abstract class or extension methods for the "defaults". However, in C#, unless your codebase already omits the
I-prefix, keep it. Just make a mental note everytime you see code like
class Something: ISomething - it means somebody isn't very good at following YAGNI and building reasonable abstractions.
 - Technically, this isn't specifically mentioned in Liskov's paper, but it is one of the foundations of the original OOP paper and in my reading of Liskov, she didn't challenge this. In a less strict interpretation (the one taken by most OOP languages), this means that any code using a public type that is intended for substitution (i.e. non-final/sealed) must work with any conforming implementation of that type.