Transient (non-equilibrium) microstructures in crystals may arise in an order-disorder phase transition that generates lattice strain. A two-phase field can develop if fluctuations of the order parameter lead to nucleation of an ordered phase in a disordered matrix, as we describe here for columbite. Synchrotron X-ray diffraction and transmission electron microscopy show that ordering in columbite involves two discrete phases with different degree of order but the same composition. A highly unusual distribution of ordered rhombic-shaped domains within a disordered matrix establishes on a nanometer scale and remains relatively stable over a prolonged period of annealing. Progressive ordering takes place within the ordered domains and the disordered matrix but the domains maintain more or less constant shape and distribution. We speculate that a new family of such microstructures could develop in other oxide phases with cation ordering transitions that are strongly first order in character. Long-term stability of such microstructures and their dependence on strain could open up the possibility of engineering the properties of crystals containing a percolating disordered matrix with ordered nanodomains of controlled dimensions.