Debes sobre escribir el metodo IsValid.

    protected override ValidationResult IsValid(object value, ValidationContext validationContext)

y retonar un ValidationResult en caso de error, en caso de que todo sea correcto retorna null.



Como debería ser tu código mas o menos:

        public class NombreApellidos : ValidationAttribute
        {
            protected override ValidationResult IsValid(object value, ValidationContext validationContext)
            {
                var v = (VmVisitaParking)validationContext.ObjectInstance;
                int idV = int.Parse(v.IdVisitanteParking.ToString());
                if (idV > 0)
                {
                    VyosaByDBEntities db = new VyosaByDBEntities();

                    var visitanteExistente = db.VisitanteParking.Where(vi => vi.IdVisitanteParking == idV).ToList();
                    v.Nombre = visitanteExistente.First().Nombre;
                    v.Apellidos = visitanteExistente.First().Apellidos;
                }
                else if (string.IsNullOrEmpty(value.ToString()))
                {
                    return new ValidationResult("Los campos apellidos y nombre son obligatorios");
                }

                return null;

            }
        }