This is somewhat of a problem as well for flight crews. Most airports do not own enough push back tractors to have one wait at all the aircraft with a bad slot. It is fairly common to have a truck at the nose wheel at STD that will wait a little while only to disappear a few seconds after the crew has called in ready and the message has been sent. There are other slotless flights in need of a push as well after all.
So if the slot then happens to improve, the search for the next available tug begins.
This is not the crews or the controllers fault; it is rather a systemic issue. The only way out of this (besides buying a truckload of pushback trucks) would be to push all the slotted aircraft clear of their nose-in position into a self-maneuvering stand where they can sit until their slot comes up; what such a system would do to airport operations is up to anyone to guess.