But I suppose appropriate heuristic solutions are typically only "pondered about" and not "found" at the whiteboard, because they require extensive testing with real-world data to see if they are actually efficient in practice.

Usually in situations like this the person asking the interview question already has already built the system in production that uses that heuristic and saw that it worked. with a good set of rules of thumb a smart person should be able to propose reasonable heuristic solutions that have a chance of working

No, that's not necessarily how it works.

Often (most?) of the time, heuristic solutions are also found by Complexity Theorists, and they usually can prove that their solution is efficient for problems with certain characteristics, e.g. random data, not random data in a particular way, etc. These are then applied by the industry when they come across problems with these characteristics.

Yes, that's simplifying the problem by making assumptions about the data. Except you often don't know what assumptions you can make. Better to check the assumptions using the data before devising an algorithm for the given type of data.

I agree in principle. But imo in reality, what actually happens is:

1. Most data sets are roughly similar (or at least fall into one of a few cases).

2. Most algorithms are designed beforehand, on ideas of what data could be, not necessarily for actual data.

Take for example sort algs. Sure, you could look at your data and devise a sort that exactly matches it most effectively. But in reality, in most cases, people just use quick sort, which is proven to be efficient on most data sets.