It turns out that the answer (to "is it possible?") is no when using the old IVsTextMarkerClient and IVsTextLines implementations.
It can be achieved by implementing the newer ITag / ITagger / ITaggerProvider interfaces instead. My current prototype looks like this:
Source code available here:
Hope it helps someone else!