これが私がコンバーターを使ってそれを解決した方法です。
指定された列を持つDataGridがあり、各列は次のように定義されています。
<MyOwn:CustomDataGridColumn Header="Column1Header" Name="Column1" ElementStyle="{StaticResource ElementStyleWithMultiConverterAndTriggers}">
    <MyOwn:CustomDataGridColumn.Binding>
        <Binding Path="RowModel.ColumnName"  ValidatesOnDataErrors="True" >
            <Binding.ValidationRules>
                <Validators:CustomCellDataInfoValidationRule />
                    </Binding.ValidationRules>
            </Binding>
    </MyOwn:CustomDataGridColumn.Binding>
</MyOwn:CustomDataGridColumn>
次に、次のようなDataTriggersを使用してスタイルを添付しました。
<Style TargetType="{x:Type TextBlock}" x:Key="ElementStyleWithMultiConverterAndTriggers">
    <Style.Resources>
        <Utils:ErrorTypeConverter x:Key="ErrorTypeConverter"/>
    </Style.Resources>
    <Setter Property="TextBlock.Padding" Value="2" />
    <Setter Property="Validation.ErrorTemplate" Value="{x:Null}" />
    <Style.Triggers>
        <DataTrigger Value="Critical" >
            <DataTrigger.Binding>
                <MultiBinding Converter="{StaticResource ErrorTypeConverter}">
                    <Binding RelativeSource="{RelativeSource FindAncestor, AncestorType={x:Type DataGridCell}}" Path="Column.Name"/>
                    <Binding Path="RowModel" /> <!--Sending the whole row object as one of the parameters to the converter-->
                </MultiBinding>
            </DataTrigger.Binding>
            <Setter Property="Background" Value="Red"/>             
        </DataTrigger>
        <DataTrigger Value="Warning" >
            <DataTrigger.Binding>
                <MultiBinding Converter="{StaticResource ErrorTypeConverter}">
                    <Binding RelativeSource="{RelativeSource FindAncestor, AncestorType={x:Type DataGridCell}}" Path="Column.Name"/>
                    <Binding Path="RowModel" />
                </MultiBinding>
            </DataTrigger.Binding>
            <Setter Property="Background" Value="Yellow"/>                              
        </DataTrigger>            
    </Style.Triggers>        
</Style>
MultiValueConverterは次のようになります。
public class ErrorTypeConverter : IMultiValueConverter
{
    public object Convert(object[] values, Type targetType, object parameter, CultureInfo culture)
    {
        var rowObject = values[1] as RowModel;
        var param = values[0].ToString();
        if (rowObject == null) return "";
        if (rowObject.ValidationClass.Any())
        {
            var validationErrors = rowObject.ValidationClass.FirstOrDefault(x => x.SourceColumn == param);
            if (validationErrors != null )
                return validationErrors.Tag; // Will return "Critical" or "Warning"
        }
        return "";
    }
    public object[] ConvertBack(object value, Type[] targetTypes, object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
} 
このスイートは私のニーズですが、検索結果に1000行以上のDataGridでは重いです。しかし、それは何もないよりはましです。どんな改善でも大歓迎です。