WPF ItemContainerStyleSelector unlimited: going data-bound

Use case
You have a View Model which contains a collection of items. In View, items are presented in an ItemsControl, say ListBox, and containers for each item should have different styles. Styles are selected depending on some property of view model items, e.g. Type property. An example of such situation is when each Type has its own combination of colors.
At this point, the task can be easily solved using a StyleSelector which encapsulates the selection logic. It's rather simple, so I won't discuss it.
To make task really interesting, let's require the selection logic to track changes in data items like Bindings do, i.e. if the value of the Type property changes, Style should be changed in the moment.