I agree with Mirage42 above, testing on 9.04 is moot. I have 9.10 Alpha 5, as updated.

Conclusions:

* The file Contents-i386.gz is still missing from the CD-ROM. I just pulled in and checked the Beta CD-ROM; it is missing there as well.

* There does not appear to be a work-around to fake the missing file, perhaps by generating the data that should be in it.

Test process:

An "apt-file update" on a new installation of apt-file (prior to adding the CD-ROM) gets me the following:

root@test2kkalpha5:~# apt-file update
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
File is up-to-date.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
File is up-to-date.
root@test2kkalpha5:~# 

Apparently apt-file is capable of working around the missing Index, and in any case that problem is not at issue here.

I then added the CD-ROM:

root@test2kkalpha5:~# apt-cdrom add
Using CD-ROM mount point /cdrom/
Unmounting CD-ROM
Waiting for disc...
Please insert a Disc in the drive and press enter 
Mounting CD-ROM...
Identifying.. [079276bebf9ed1e0b82897bd213817c8-2]
Scanning disc for index files..
Found 2 package indexes, 0 source indexes, 0 translation indexes and 1 signatures
This disc is called: 
'Ubuntu 9.10 _Karmic Koala_ - Alpha i386 (20090902.1)'
Copying package lists...gpgv: Signature made Wed 02 Sep 2009 12:03:07 PM MDT using DSA key ID FBB75451
gpgv: Good signature from "Ubuntu CD Image Automatic Signing Key <email address hidden>"
Reading Package Indexes... Done
Writing new source list
Source list entries for this disc are:
deb cdrom:[Ubuntu 9.10 _Karmic Koala_ - Alpha i386 (20090902.1)]/ karmic main restricted
Unmounting CD-ROM...
Repeat this process for the rest of the CDs in your set.
W: Skipping non-exisiting file /cdrom/dists/karmic/main/binary-i386/Packages
W: Skipping non-exisiting file /cdrom/dists/karmic/restricted/binary-i386/Packages
root@test2kkalpha5:~# 

I then re-ran the update:

root@test2kkalpha5:~# apt-file update
Put CDROM labeled [Ubuntu_9.10__Karmic_Koala__-_Alpha_i386_(20090902.1)] in the cdrom device
read: 1: arg count
mount: block device /dev/sr0 is write-protected, mounting read-only
cp: cannot stat `/cdrom/dists/karmic/Contents-i386.gz': No such file or directory
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-updates/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
File is up-to-date.
Downloading Index http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.diff/Index:
No Index available.
Downloading complete file http://mirrors.xmission.com/ubuntu/dists/karmic-security/Contents-i386.gz
File is up-to-date.
root@test2kkalpha5:~# 

Apt-file works for packages delivered over the Internet:

root@test2kkalpha5:~# apt-file list apt-file
apt-file: /etc/apt/apt-file.conf
apt-file: /etc/bash_completion.d/apt-file
apt-file: /usr/bin/apt-file
apt-file: /usr/bin/diffindex-download
apt-file: /usr/bin/diffindex-rred
apt-file: /usr/share/apt-file/apt-file-update.update-notifier
apt-file: /usr/share/apt-file/do-apt-file-update
apt-file: /usr/share/apt-file/is-cache-empty
apt-file: /usr/share/doc/apt-file/README
apt-file: /usr/share/doc/apt-file/changelog.gz
apt-file: /usr/share/doc/apt-file/copyright
apt-file: /usr/share/man/man1/apt-file.1.gz
apt-file: /usr/share/man/man1/diffindex-download.1.gz
apt-file: /usr/share/man/man1/diffindex-rred.1.gz
root@test2kkalpha5:~# 

Can you suggest a package that was installed from the CD-ROM and has not been updated from the net? It occurs to me that a fresh installation with no updates from the net would work, but (sorry) I can't do that right now. Let me see what I can do in the next few days.