I don't see how you will have a problem which is progress free but still in NP(requirement 7); or any kind of problem that is suitable for your purpose for that matter. To see why this seems unlikely lets consider the solution space for your problem as I start and when I have progressed in an arbitrary algorithm that searches the solution space. when I start the entire solution space given by your problem formulation is unexplored, However as soon as I start searching I know the best value and what solutions I have investigated before. This reduces the solution space. If I don't do this I run the risk of repeating solutions to no avail. therefore I suspect there is no optimal time non -stochastic algorithm which does not change the solution space in the sense that it records its own progress. Therefore I suspect there is no problem for which a solution can be found for sure that has the desired property. This in combination with the requirement that the problem should be scalable(so there is no guarantee that only large problems will be used) makes it hard to have any real solutions to this problem
If your drop this requirement, travelling salesman problems for random regions might be interesting since This could help transport companies alot while offering a huge potential number of problems that are highly customizable. However use would be somewhat limited since it would be quite random what TSPs would be solved. However It would be quite nice to have a database in which you enter some cities and a maximum distance and get a route between them that is shorter than that distance. you could for example use the 3000 largest cities on earth and compute random TSPs with those.
Another possibility is approximations of the Navier stokes equations for typical requirements. But this is somewhat outside my field
Not being able to coordinate which problems are solved when is a major problem for the usefullness, so all problems that have these kind of properties should be problems which are in general very useful. I think TSP problems with a pool of the 3000 largest cities in the world would have this property, but still alot of computations would be useless. minimum k-cut problems for computer design could also be useful as long as you can find a sub set of these problems that have a high chance of being useful, which I think is possible, but I know too little abnout chip design to find it myself. same thing for SAT problems.
I am not sure how to guarantee property 8, so I have not included that in my analysis.
edited for (hopefully) more relevance
A useful problem for cryptography could be SAT since boolean statisfiability can be easily re-written into most cryptography problems. However, the problem is still that there is no central authority to generate the problem and so finding a relevant SAT problem is much harder than it appears. One idea maybe is to not have one authority but instead some huge database of useful SAT instances where one is randomly pulled from. If the randomizer is apt precomputation is impossible.