Congratulations - a just reward for perseverance.
re RAM and speeds
I looked at the HP QuickSpecs doc on the nx9040. There are several, one of which outlines the range of cpu fitted as standard. For all models, apparently, the spec is :
Two 266-MHz DDR memory slots with support for up to 2048 MB (configurations offered up to 1024 MB)
So I assumed you had 266MHz RAM.
For pricing, I did the very quickest of looks on eBay for DDR 266 and saw 1GB SODIMMs at inexpensive prices. (Not profound research, I know. I gave 333 no thought at all.)
Was your 333 SODIMM fitted standard ? Quite possibly. The following comment appears later in the spec doc.
Standard Configurable from 128 to 1024 MB 266-MHz DDR
Maximum 2048-MB 266-MHz DDR SDRAM
NOTE: Uses PC 2700 DDR 333MHz memory module but system runs at 266MHz.
Apart from HP reckoning that you would be best to choose HP RAM (surprise !), there is no further note in the spec on this topic.
The HP website has notes on upgrading RAM, here :
https://h20566.www2.hp.com/hpsc/doc/public/display?sp4ts.oid=428120&docId=emr_na-c00820047&docLocale=en_US If they do have a definitive view on 266 v 333, then it might be in this area. (It needs your specific model number to start.)
Hope that clarifies, and saves you some searching.