Проблема в вашем коде состоит в том, что установка значения Visibility в самом текстовом блоке имеет более высокий приоритет, чем установка в стиле. Таким образом, даже когда срабатывает триггер, настройки внутри триггера не действуют. Измените XAML на:
<TextBlock Margin="4" FontStyle="Italic" FontSize="12" Text="List is empty" >
<TextBlock.Style>
<Style TargetType="{x:Type TextBlock}">
<Setter Property="Visibility" Value="Collapsed" />
<Style.Triggers>
<DataTrigger Binding="{Binding ElementName=lstItems, Path=Items.Count}" Value="0">
<Setter Property="Visibility" Value="Visible" />
</DataTrigger>
</Style.Triggers>
</Style>
</TextBlock.Style>
</TextBlock>
Где настройка Visibility полностью в стиле и работает (по крайней мере, в моем демонстрационном проекте).