Ok, I used the offline patch that jamyskis provided a link for:
http://www.magnetoid.com/RoL_Patches.7z To my surprise, I seem to have the US version of the game, at least according to the sticker at the back of my CD box: "For distribution in US/Canada only.". Huh?
So, I had to use the extra instructions for the US version, ie. using the US-only bat-file, and copy also the one extra US-specific RTP file into the patches directory, in addition to the European patches.
The patching seemed to go ok. I think it said 44 added files, and 7 something else. Now the version is listed as 0.0704.1001.0000.13.0, previously it was 0.0604.1602.0000 I think. For now I tried the patching only in Windows XP; Vista and 7 may need some extra care, like installing the game to somewhere else besides Program Files, and running the bat file as admin.
It should be noted that according to some remarks on internet, some EU versions of the game may be up to date to the latest version already, ie. 0.0704.1001.0000 (or 0.0704.1001.0000.13.0, doesn't matter which one).
Now I should check if this same applies to the first Rise of Nations (Gold) game, because I think it didn't have offline patches either. :( But I _think_ I tried to update it earlier online, and it worked? So it might be that for it the update server is still online, but not for the sequel. Odd.
EDIT: Confirmed that for the earlier game, Rise of Nations (Gold), the update servers still seem to be online. I had no problem updating RoN Gold. I wish it had an offline patch too, though. But for this seque, Rise of Legends, the update servers are offline.
Damn useless umbilical cords...