Hi Kristina,
One thing that we need to consider is the size of the lists and where those lists are located(same site or different sites).
If the lists are each over 5,000 items then we should expect a performance degradation searching.
One important thing is the SharePoint version. SharePoint 2010 manages better large lists than SharePoint 2007.