<p>We need to get all the instances of objects that implement a given interface - can we do that, and if so how?</p>

I don't believe there is a way... You would have to either be able to walk the Heap, and examine every object there, or walk the stack of every active thread in the application process space, examining every stack reference variable on every thread...
The other way, (I am guessing you can't do) is intercept all Object creation activities (using a container approach) and keep a list of all objects in your application...