Hmmm interesting....

What about a hybrid solution perhaps, whereby the initial query plan provided is as is currently I.E. a good enough plan is provided quickly, whilst in the background SQL Server continues to calculate what is "the" most optimal plan.