For the table I'm not actually using "TD WIDTH=***" codes. I only set the main table width to 100% (to use all available space).

IE4 will always make a table bigger than it should be if the graphics inside don't fit - so the NEW graphic should **always** show, no matter what the widths are. If it's not showing, all I can think of is that it's either a bug in your particular version of IE4, or perhaps a problem with the display driver. I'm betting on the latter - I've noticed a few display problems with a new version of my display driver that didn't happen on the previous version as well.