I think what you are experiencing is one of the most common limitations of Quake3's shitty handling of skyboxes. Everything that is present in your current PVS will be shown through the skybox. The only thing that really helps here is to get the offending part of the map out of the current PVS. Hint brushes, redoing the layout, that sort of thing, although in your case, rebuilding looks the be only viable option.