...so some sort of global search isnt really practical (and would defeat the point somewhat).
In theory: yes, you are right. In practice: It's a very cheap operation. What i'm actually doing is this: I detect which sectors are visible (or covered by an object for collision detection in that case) and store them in a list. Then i'm iterating through the objects that are attached to my world-object (i'm doing this anyway) and simply ask them, if they are in one of the relevant sectors. If they are, they need further processing (rendering, collision detection...). This is really a very cheap operation and nothing compared to the more advanced operations that are happening later in the pipeline (per polygon and even per pixel because it's a software renderer).
What i'm not doing is to collect all objects that belong to a specific sector. I simply don't need this information. My portals are an option, not a must. You can build a level without using a single portal (you don't even have to care about the fact that they are an option...you can just ignore them completely). This will be slower of course, but it's possible.