The firmware only updates when the provider pushes an update. However, that won't affect the menus; that's software which is loaded as part of the netboot phase. The features you'll have will depend on whose software they're running on the box. Sounds like you probably got something other than SA's SARA software, so it doesn't have that feature.
If VOD is important, you could still have a plain cable box just for VOD, and get a TiVo for recording. It's not the best, but it at least gets you where you want to go.