Is the Last-Modified HTTP header required for browser caching?

Be wary of reading random articles on the net (although Mark Nottingham's stuff is usually sensible). The definitive source should always by the RFCs. And according to RFC 2616 a browser should cache a document with an Expires: header where the timestamp is in the future, or where other valid caching instructions are provided provided that the document is not returned in response to a POST request.

It's perfectly valid to set a max-age without a last-modified - and the spec explicitly addresses that.

Certainly what you describe seems very unusual and implies that FF4.01 will never cache content - I would be amazed that it passed the QC checks with such a glaring omission. Can you provide details of the requests and responses proving this (e.g. with liveheaders)?