When Microsoft developed Windows Vista, they were intending to address one of the main issues with Windows XP, security. One of the ways they did this was to make it very difficult for programs to access your files, which obviously messes around with Civilization III. Assuming you are running default security settings, a program needs administrator permission in order to access C:/Program Files or C:/Program Files(x86). This is why, when installing new programs, you will get a popup saying "Do you want to allow this program to make changes to your computer?".
If you write a document in Microsoft Word, edit photos from your latest vacation, or even play a game of Civilization IV, these programs by default will save files to some destination in your user folder, which is of course allowed. However, if you try to make a Notepad file in the your Program Files folder, you will get a popup saying "Access is denied". This is because Notepad does not have the administrator permission required to access Program Files.
Of course, all of the programs mentioned above were made after Windows Vista, and made the User folder the default destination for saved files. Civilization III, however, was made back in the day when games (or scenarios) being saved directly within Program Files was all fine and good. This was the norm at the time for games, and Microsoft was well aware of that when they made Vista. To make sure that older games like Civilization III still worked Microsoft created a directory called VirtualStore. This folder, hidden deep inside the User directory, essentially emulates the Program Files folder. Thus, when you go to save your game, it is actually saving it within the VirtualStore, and when you load a game, it looks in the VirtualStore as well. You won't even notice unless you try to access the saves outside of the game. (Which had me banging my head against the wall the first time I tried to play a Succession Game on Windows 7).
So if you want to access the saves, you have three solutions:
1) Do what Lanzelot said and install the game outside of Program Files. This is the wisest and simplest option, but it is not possible if you have already installed the game.
2) Manually find your saves which should be in this location:
C:/Users/<UserName>/AppData*/Local/VirtualStore/<Publisher>/Civilization III/Conquests/Saves
<UserName> is your user name, and <Publisher> is the publisher of your copy, it should be either Infogrames Interactive, Atari or 2K Games.
*Do note that AppData is a hidden folder, and you will have to set Windows Explorer to show these.
3) Run Civilization III as an administrator. Your account has to be an administrator account to do this, obviously. Right-click on your Civilization III icon, and select the "Run as administrator" option with the little shield beside it. This will produce the "Do you want to allow this program to make changes to your computer?" popup, which you answer "yes" to. Civilization III will then start saving and loading files from the default Program Files destination.
Keep in mind though, that the editor is a separate program, which you will also have to give admin rights to. If you don't, then the editor will continue to save files in the VirtualStore, and your game will not find them. I suspect that this is your problem, Vaney and Registrar. For the game to be able to read scenario files, they must be in the folder corresponding to whether or not the game has admin rights.