There's a hardware feature called 'occlusion queries', which do exactly what you're looking for -- determine a yes/no answer to whether something was drawn or not. To find out if there's "holes" in the depth buffer, you can draw a quad that's very far away using an occlusion query, and check if the result is "yes - the quad was visible".

Now I get to my idea - display few partitions, then CHECK IF ALL PIXELS WERE DISPLAYED, if not, display some more partitions, and so on. That could make it really fast, cause it would cut of everything excpet the first room. Problém is that extracting depth buffer and checking all the 1920x1080 of that little guys is so slow that it would be contraproductive (proven by try).

A bigger problem is that the CPU and GPU have a very large latency between them. When you call any glDraw function, the driver is actually writing a command packet into a queue (like networking!), and the GPU might not execute that command until, say, 30ms later. This is perfectly fine in most situations, as the CPU and GPU form a pipeline with huge throughput, but long latency.
e.g. a healthy timeline looks like:

CPU: | Frame 1 | Frame 2 | Frame 3 | ...
GPU: | wait    | Frame 1 | Frame 2 | ...

If you ever try to read GPU data back to the CPU during a frame -- e.g. you split your frame into two parts (A/B) with a read-back operation in between them, you end up with a timeline like this:

CPU: | Frame1.A | wait      |Copy| Frame1.B | Frame2.A | wait      |Copy| Frame2.B | Frame3.A | ...
GPU: | wait     | Frame 1.A |Copy| wait     | Frame1.B | Frame 2.A |Copy| wait     | Frame2.B | ...

Now, both the CPU and GPU spend roughly half of the time idle, waiting on the other processor.
If you're going to read back GPU data, you need to wait at least one frame before requesting the results, to avoid causing a pipeline bubble :(
That means that reading back GPU data to use in CPU-driven occlusion culling is a dead-end for performance.

"Thousands of triangles" should not be something that alters the framerate so dramatically. A modern game can draw hundreds of thousands of triangles at 1000fps -- which is one of the reasons that VBO's replaced begin/end (same number of gl function calls required for any number of triangles).

You need to profile your game to find out where the time is being spent. Set up a class that records the high-frequency timer at two points in time, subtracts the difference, and logs the result, and then put instances of this class in any function that you think might be a performance hog.

It's common to do this with a constructor/destructor:

struct ProfileLogger { ProfileLogger(const char* name) { PushProfileScope(name); } ~ProfileLogger() { PopProfileScope(); } };
#define Profile(name) ProfileLogger _profile_(name);
 
void Test()
{
  Profile("Test");// calls PushProfileScope("Test") here
  DoStuff();
}// calls PopProfileScope("Test") here

From this data you can get a hierarchical breakdown of where all your CPU time is spent per frame. Trying to optimize without this data is just shooting in the dark.

From the sounds of it, your game is almost certainly CPU-bound, so you can start here. Later on though, you can use gl timer queries to do the same thing on the GPU side -- wrapping parts of the scene in two timer queries to find out how long it took the GPU to process those commands.

The problem with this use of occlusion queries is the pipeline bubble caused by reading back results on the same frame. Even if the query itself is free, this bubble will halve your framerate.

Reading back an occlusion query is fine if you wait one frame before requesting the result, as this won't disrupt the pipeline. This is useful for things like lens flares or special effects where you don't care about the data being one frame old, but is dangerous for deciding what parts of the scene to draw :(

Generally they're a pretty useless API feature...

In a modern engine though, you can move all your culling and "what to draw" code off the CPU and into a compute shader. You can then issue draw-indirect commands to say "you will be drawing something, but I don't know which triangles, yet. The number and offset will be present in this buffer later (which is filled in by the compute shader).

For something like a quake3 level though, you should be able to have a constant draw cost regardless of how many triangles are visible. The level triangle data is static, so put it in a VBO once and never update it again.

Since you're using a Quake 3 map, the classic Quake method of solving this was to precompute a potentially visible set (or PVS) using an offline pre-processor, then do checks against that PVS at runtime to determine what should (or should not) be drawn.

In (very basic) outline, you divide your map into what I'll call "areas"; these could be nodes/leafs in a BSP tree (which was what Quake used), rooms, cubes in a grid, whatever. Then for each such area, you use some brute-force method to determine what other areas are potentially visible from it (I believe that the "potentially" part is on account of some coarseness in the algorithm, as well as the fact that this stage ignores frustum culling which is still done at runtime). Store out the result in some fast and compact data format (Quake used a bitfield array). Then at runtime you're just looking up those stored results, draw calls, overdraw, etc all go down, the map runs faster, and everbody is happy.

The downside is that the pre-processing can take time, needs to be re-run even if you make trivial changes to your map, and needs a custom map format to store the data. And while we're on the subject of formats, .obj is a horrible, horrible, horrible, horrible, horrible format to use for game maps. The only reason to use it is if you really love writing text parsers. The ideal format is where you memory-map a file, read some headers to set up some sizes, then glBufferData the rest. Simple, quick to load, no faffing about. And while we're on the subject of glBufferData, if your observation is that VBOs are slower than glBegin/glEnd, then you're using them wrong: probably by writing a glBegin/glEnd-alike wrapper around the VBO API.