You need more ram, I have as background process about 400MB and with Quake 4 I can reach 1.25GB and even more.
Also ultra settings will uncompress all the textures, about 500MB , so if you have only 256MB video ram, the other frame buffer will go to your system RAM, and when you reach the limit, will start to allocate on your virtual memory, your hard drive, so you will have to wait for the writing time.
Some people think 512mb is for those with high resolutions, but many games are pushing bigger textures, so you need more video ram.
Examples of games that require 512MB video ram are: Doom 3, Quake 4, Ghost Recon Advanced Warfighter and Tomb Raider Legends (Next gen setting on).
On Quake, you can try with a lower resolution or get more ram.