Continuous Clustering
There's a fair amount of work on stream clustering (which is slightly different to online methods, but is essentially what you want). The above reference by Guha et al is a very good one, and for a more general perspective on what kinds of techniques work, and what methods have been used in the past (both heuristic and precise), you might want to look at my survey on clustering on streams.