I wonder if this imbalance of the number of rows maybe a result of the Timeout
Almost without exception, no. An initial cardinality estimation is performed before optimization begins. Subsequent optimizer transformations may require new estimates to be computed. There is no general rule to say which of the estimates will be more "accurate".
See this related question for additional information about the Timeout reason:
Queries without Good Enough Plan Found
I thought it should be appropriate after the index & statistics rebuilding?
You have "a very complex ugly query". It is unreasonable to expect the cardinality estimator to work well in such cases. Try computing estimates yourself from the single-column (possibly sampled) statistics histograms and single-value density information to get a feeling for this.
As query complexity builds, so the quality of estimates tends to go down. This is inevitable, if you consider that the input to one estimation is usually the output of another. Thus, errors tend to accumulate. This is made much worse by the use of "ugly" (read: non-relational or otherwise hard-to-estimate) conditions.
Does optimizing queries that end with ReasonForEarlyTermination=Timeout make any sense at all, if it's impossible to change the query itself?
Sure (but no differently than for any other problematic plan). In general, one can break the query up, express it using different syntax, or any one of a hundred different "tricks" may be used.
Even where the query itself cannot be changed, if a good plan can be found, it can be forced with a plan guide. More generally, adding new statistics and/or indexes can provide better information to the optimizer and cardinality estimator. This can also affect the code path taken through the optimizer in complex ways. I will not attempt to list all the things that can be done outside of changing the query text.
...the next query plan creation will certainly timeout again and so might be different, with different results?
The point is that by providing better information or data access methods, you will generally improve your chances of getting a good plan. The optimizer is not random, so for a given state of the database, the same plan will be selected, regardless of timeout, or other termination reason.
The real key to success is to avoid "very complex ugly" queries, of course.
