How to construct a running kd-tree?
How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key.
The maximum depth is determined by the number of bits. If x, y and t each have 32 bits, the depth is limited to 3*32=96 bits. Usually the depth is much less, because depth is solely determined by the type of data, not by the insertion order. Insertion and deletion time does also not change over time, only with the size of the tree.

The bit-interleaving imposes a z-order on the tree which helps with window queries by roughly translating spatial proximity into neighbourness in the tree.

A Java example, with support for kD-window queries, can be found here (my own code). THis also contains code to do the bit-interleaving, also for floating-point values. 

If you do bit-interleaving, it may be worthwhile to transform the coordinates to a similar value range. For example if x and y range from 0 to 10000, then it may be useful to multiply and/or add a constant to t, such that it also ranges from 0-10000 (you can also transform x,y instead). This is not essential. You may also want to use t as the first dimension, because it sounds like you perform a lot of window queries over t to remove old values. Having t as first dimension should improve such queries. 

If you are looking for something more sophisticated, especially with more dimensions or large datasets, there is the PH-Tree. It is similar to a bitwise trie, but uses larger nodes like a quadtree, so the maximum depth is more limited. The linked website also links sourcecode and a description, including a performance comparison of kDtree, bitwise tries (critbit tree) and PH-Tree.

Disclaimer: The last part is basically self-advertising, but to the best of my knowledge, the PH-tree may be the best solution in your case, at least if you have large datasets.