I've been using SharePoint Cross List Queries in multiple places in a recent site development project and I've noticed that no matter how you use them with indexed columns or without indexed columns or any other settings these monsters consume huge amounts of memory and are extermely slow. So unless you have a small number of lists and not a lot of items in each list you shouldn't be using them.
In a recent project I was using SharePoint queries to fetch latest posts based on a selection & filtering algorithm from SharePoint forums. Now we had a huge number of forums each located in different sub sites and we needed to run a query where we could get the latest post that matched a specific criteria. Once the system grew to a huge amount of data we realized that the Cross List queries were running very slow and at one point we started getting "Server Out of Memory" exceptions. So to cut a long story short we eventually had to create SharePoint events put them on list adding, updating & deleting events and replicate the fields needed in a SQL table and then run our query on the table.
My personal on why SharePoint Cross List Queries suck in performance: I think when Microsoft developed this feature they only had small lists or a small number of lists in mind plus they also had to make sure that this feature was compatible with other SharePoint features (like list item level security) so they couldn't just translate the CAML in cross list query to a SQL statement and run it on the DB even when you have configured all the columns in your query as indexed columns. So what happens is SharePoint loads all the data related to those lists into memory, sorts them, tries to filter them and then you get a Server out of memory exception on large amounts of data.