Users want to create tables with many columns and infinite scrolling rows – how do we handle this?

I have a situation where users are capable of creating their own searches on extensive data sets, using a query-like user interface. Our users come from a strong Excel background and are used to working with dozens or more columns in those.

Our search system provides a full screen interface with infinite scrolling and fixed headers, as sometimes these searches can return millions of records. We tested limiting the number of columns on a search to 12, but users were vocal about their desire to have more.

We get asked to add horizontal scrolling, but this works poorly with the existing system of fixed headers and infinite scrolling, in addition to generally making for a poor user experience.

Because the users select the columns themselves and can write custom columns using mathematical functions or aggregates on previous columns, it is difficult to predict the final appearance or content of the searches and not likely possible to condense multiple columns into a single cell.

Are there any patterns or shortcuts to provide what the customer is asking for without compromising experience or functionality?