I had the same problem after applying the Microsoft Sept. 10, 2003
security update KB824146. [It is possible that the problem started
after applying a different update, but I think it was KB824146 that
caused it.]

After the update the Paper Size option [under Page Setup] in
Internet Explorer only had:
16K
Ariel
B5
Executive(JIS)

The machine was Win2000, SP2. IE 5.5 SP1

I first updated IE to 6 and the problem remained.

I then did several windows update patches. Those updates we
cumulative patch IE6 SP1 (822925)
330994: April 2003 Security Update OE 6 SP1
Q329115: Security Update (win2000)
814078: Security Update (MS Jscript ver 5.6)
Security Update, Feb 13, 2002 (MSXML 3.0)

The problem was still there, so I did the new Win2000 SP4, and
all the paper sizes returned!!

-- Doug

jeff wrote:

After applying Windows updates, the options of letter,
legal, etc. do not exist under File..Page Setup..Paper
Size within Excel for any printers installed on this PC.
The only entry in the drop-down list is A4. I feel that
the updates caused this problem, because this particular
worksheet is printed daily. The updates were applied on
Monday PM and the problem started on Tuesday AM. This
particular PC was missing several security updates
(including the patch for LovSan), so there were multiple
updates applied. This PC is running MS Office 2000 (SP3)
and Win2000 (SP2). Anyone have any ideas on this?