We capture the states of the whole pipeline in a StateBlock before rendering our UI, and restore the states after it's done.
However, we didn't properly call Release() on this IDirect3DStateBlock9 when the application exits.
According to DirectX docs, plus an educated guess, I believe that this StateBlock holds a reference to basically every resource that's current bound to the driver, including all vertex streams, textures for all sampling stages, vertex and pixel shaders, etc. If you fail to release the StateBlock, all these resources won't get released. This perfectly explained why some of our vertex declarations and cubemaps leak even if we called Release() on them.
Thank you guys for providing valuable opinions along the way!