Customer creates a Records Center site collection as a centralized place for archived documents and they don't want to include archived documents in the global search results (All Sites search) even when the user has the right permission to access these documents, but the content should still be available if user goes to the site and does a local search there (This Site search).
Also customer uses single SSP, single Web Application for Records Center site collection and Portal. Creating a separate SSP for this scenario is a little bit overkill.
I did some research and seemed like most of the search settings are all global like Crawl Rule in Search Settings in SSP admin, Search Visibility in Site Administration, etc. If I exclude this site collection from being crawled, then I can't search locally from within Records Center site either.
Eventually a Search expert directed me to the right place and the solution was quite simple actually. It should apply to many other common scenarios when you want to hide certain site collections from global search while not their own local search.
Here's the solution: