Ok, então quando eu quiser que uma propriedade seja validada, eu posso escrever algo assim:

    [Required]
    [StringLength(255)]
    [DataType(DataType.EmailAddress)]
    [RegularExpression(RegexStrings.Email, ErrorMessage = "Email is not valid.")]
    [DataMember(IsRequired = true, Name="Email", Order = 1)]
    public string Email { get; set; }

Eu gosto disso porque neste caso, eu aponto para as strings regex que temos em nossa biblioteca comum e especifico uma mensagem de erro se falhar. Simples e limpo.

Minha situação é essa. Isso está em um serviço RESTful do WCF. Uma das propriedades que eu quero validardesta maneira precisa ser validado usando um método customizado que valida o uso de alguma lógica de negócios (verifica o tamanho da string e o tamanho do byte). Posso (e como faço) configurar esta validação customizada para que eu possa usá-la como é usado no exemplo acima; então parece algo como:

[StreamValidation(ValidationClass, ErrorMessage = "Serial number is invalid")]
public string Ksn { get; set; }

ATUALIZAR:

Eu construí a seguinte classe para ser meu atributo:

[AttributeUsage(AttributeTargets.Property | AttributeTargets.Field, AllowMultiple = false)]
public class KsnValidation : ValidationAttribute
{
    public override bool IsValid(object value)
    {
        if (!(value is string)) return false;

        var val = (string) value;
        var bytes = Enumerable
            .Range(0, val.Length / 2)
            .Select(x => Byte.Parse(val.Substring(2 * x, 2), NumberStyles.HexNumber))
            .ToArray();
        return val.Length == 20 && bytes.Length == 10;
    }

    public override string FormatErrorMessage(string name)
    {
        return base.FormatErrorMessage(name);
    }
}

Em seguida, decorou a seguinte propriedade:

[KsnValidation(ErrorMessage = "Wrong Name")]
public string Ksn { get; set; }

Mas não tenho certeza de como testar essa unidade