When following SRP, how should I deal with validating and saving entities?

Question

I've been reading Clean Code and various online articles about SOLID lately, and the more I read about it, the more I feel like I don't know anything.

Let's say I'm building a web application using ASP.NET MVC 3. Let's say I have a UsersController with a Create action like this:

public class UsersController : Controller
{
    public ActionResult Create(CreateUserViewModel viewModel)
    {

    }
}

In that action method I want to save a user to the database if the data that was entered is valid.

Now, according to the Single Responsibility Principle an object should have a single responsibility, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility. Since validation and saving to the database are two separate responsibilities, I guess I should create to separate class to handle them like this:

public class UsersController : Controller
{
    private ICreateUserValidator validator;
    private IUserService service;

    public UsersController(ICreateUserValidator validator, IUserService service)
    {
        this.validator = validator;
        this.service= service;
    }

    public ActionResult Create(CreateUserViewModel viewModel)
    {
        ValidationResult result = validator.IsValid(viewModel);

        if (result.IsValid)
        {
            service.CreateUser(viewModel);
            return RedirectToAction("Index");
        }
        else
        {
            foreach (var errorMessage in result.ErrorMessages)
            {
                ModelState.AddModelError(String.Empty, errorMessage);
            }
            return View(viewModel);
        }
    }
}

That makes some sense to me, but I'm not at all sure that this is the right way to handle things like this. It is for example entirely possible to pass an invalid instance of CreateUserViewModel to the IUserService class. I know I could use the built in DataAnnotations, but what when they aren't enough? Image that my ICreateUserValidator checks the database to see if there already is another user with the same name...

Another option is to let the IUserService take care of the validation like this:

public class UserService : IUserService
{
    private ICreateUserValidator validator;

    public UserService(ICreateUserValidator validator)
    {
        this.validator = validator;
    }

    public ValidationResult CreateUser(CreateUserViewModel viewModel)
    {
        var result = validator.IsValid(viewModel);

        if (result.IsValid)
        {
            // Save the user
        }

        return result;
    }
}

But I feel I'm violating the Single Responsibility Principle here.

How should I deal with something like this?