I don't think that setting is actually on your device. I think VM settings are made over the phone while acessing your VM box. On my carrier, after I've dialed my VM box there are prompts to change the "settings" (like outgoing message etc). I don't know if there is one to choose a time/date stamp though. I kind of thought that was automatic. But, that's where I'd look.
Devices: T-Mobile MDA (Cingular SIM), i-mate SP5m (sitting in a drawer at the moment while I attempt to migrate to PPC permanently), Cingular 3125 (unlocked and in use on T-Mobile), Motorola MPx220 (retired), Motorola MPx200 (retired)
Accessories: Plantronics Explorer 330 & 2G Patriot Micro-SD (use w/MDA), Kingston 2G mini-SD used in SP5m, Plantronics Discovery 640 & 2G San Disk micro-SD (use w/3125), Jabra A210 BT adapter + Motorola HS805 (retired)