I'm probably telling you nothing you've not tried already but as far as I know MSConfig is on all versions of Vista and Windows since 98' (maybe earlier I'm not certain) it's in the same folder (C:\Windows\System32)
Vista is tied down more securly (or is that anally!!) than XP so it maybe hidden from view as the C:\Windows\System32 folder by default is a hidden system folder so may not be seen by the Vista search.
Few suggestions I can think of
1 - browse to the folder and make sure you can see msconfig.exe in the list
2 - make sure in the tools/folder options/view that hidden files and system files is unchecked to make certain it's not been hidden from view for some reason
3- have you tried to just use run
4 Last but not least it should be available on the original windows disk - not sure on vista if this would be a windows add-in or in what use to be the valueadd folder on XP Install CD
Failing that found the site below - it's for XP but may give some more things to try
But just to confirm Vista 64-bit Ultimate edition still has it
Google 'msconfig virus' and you will get many hits. I hesitate to point to one because there are so many possibities not the least of which is that it got infected and your av quarrantined it.