Well, to close this thread:
Norf dude has a HP Pavillon T3434 PC with an ATI Radeon Express 200 running with Win XP SP2. In the BIOS setup it wasnt possible to give the VGA more than 64MB RAM. I told him to contact the HP support, what he allegedly did and allegedly was told his warranty is lost because he already entered setup

Nice story.
So I still don't know does HP just lie when indicating "up to 256MB" on the product specifications, is there kinda bug in the system setup or whatever. Woud be grateful if someone knows about this PC model and would tell me. Yet I don't know if Norf's VGA claims 256 or 64MB. He almost couldnt manage anything hardware-side.
What he finally managed was to lower the video settings in the game and now he's able to play. So at least we can say the ATI Radeon Express 200 is a rare case of on Board VGA which can run Nexuiz fluently.