Consider:
http://stackoverflow.com/questions/21697/how-do-you-communicate-service-layer-messages-errors-to-higher-layers-using-mvp
I'm not sure how to help specifically here. First, I don't really understand your setup, or know anything about WCF particulars. Second, I don't really get the comment about disliking exceptions for biz logic... but I'm assuming you mean "business validation" as you stated elsewhere (in which case, that makes sense to me).
In my ignorance, it looks like you've got the start of your own scheme going, so maybe you've got a lot of freedom. And certainly a lot of things could work. So, here are some alternatives:
Method of Communication
You might just try your approach and see how you like it. IMO, it's mixing concerns a little to validate and operate together (sometime it can't be helped, esp. if you start asking how to handle failures). Command-Query, stuff aside, this is a classic return-vs-throw issue and, at this boundary, you're within rights to choose either as long as it works.
If you have a framework for your MVP, you might see if it has anything built in.
Barring that, you could change your PL/SL relationship to separate validation explicitly from the operation. Like so:
IList<Error> Validate_Operation1(Entity1 a){}
Entity2 Operation1(Entity1 a){}
Or, to be way crazy:
public interface ICommand
{
IList<Param> Params { set; }
IList<Error> Validate();
void Execute();
}
If I was firmly differentiating "Validation Errors" apart from "Post-Validation Errors" and "Unexpected Errors", I might do the above. Getting validation problems back as a result of asking for validation certainly isn't "exceptional".
All that aside, you might consider getting a little more abstract into what you're going to do with post-validation errors. Some of these you may be user-actionable, whether or not they're biz related. "Datatraveler appears corrupt. Please reformat thumbdrive." Or even warnings like "Preferences not found, completed with defaults." If your app is highly interactive, your chatty SL might use the more general mechanism to send back validation issues.
Content of Communication
I don't see your Response-class-with-error-enums-and-null-entities as being miles different from defining your own error class or exception, honestly. I'm not big on a "multi-purpose" return like this but there's a case for that approach: Many EventArgs or async callback args are implemented to have the error, cancel, and results information.
Regarding your listed drawback, I'm not sure how broad the error hierarchy is when you say "the PL needs to handle all the cases defined in exceptionInfo", so forgive me for assuming the worst here. The vehicle you choose (exceptions, plain strings, or an exceptionInfo enum) doesn't change the fact that, if you recognize 762 distinct errors, you recognize 762 distinct errors.
But that doesn't mean your presenters need to account for every one explicitly. You've got the benefit of context - you know you aren't going to get "Username was blank" after the user's already logged in and is checking their mortgage balance. (And if you do, you should probably treat that as "Unexpected error while checking balance. Please try again later." and log the call stack, right?)
So your presenter only needs to know the shorter list that applies to its context, not all of them. Everything else is "Unexpected ...".
And, since you're defining your own Error class, you might consider putting your errors in string resources and tying the resource ID to the specific error when you create the object. Then, instead of individually handling the cases, many of them can be resolve by the same action: Get ID, load string, show string, done. No switch-statement required.