Multi-res bilateral?
Bilateral filter downsample, fill / iterate and then a joint upsample (somehow). This process should be fast and might improve results given that the effects of bad depth boundaries will be reduced at lower resolutions, as well as allowing much larger areas to potentially participate in filling gaps. The upscale must then merge / use the higher resolution depth information somehow. Potentially a different approach to colour+distance weighting will be required to prevent unwanted influence from really distance points.