When EC2 first started the mental model was of a magic Pez dispenser supplying an infinite stream of instances in any desired flavor. If you needed an instance, because of a either a failure or traffic spike, it would be there. As amazing as EC2 is, this model turned out to be optimistic.  

From a thread on the Amazon discussion forum we learn any dispenser has limits:

As Availability Zones grow over time, our ability to continue to expand them can become constrained. In these scenarios, we will prevent customers from launching in the constrained zone if they do not yet have existing resources in that zone. We also might remove the constrained zone entirely from the list of options for new customers. This means that occasionally, different customers will see a different number of Availability Zones in a particular Region. Both approaches aim to help customers avoid accidentally starting to build up their infrastructure in an Availability Zone where they might have less ability to expand.

The solution: if you need guaranteed resources in different zones, purchase Reserved Instances. This will assure capacity when needed. There's no way to know if the instance types you are interested in are available in an availability zone, so reserving instances is the only solution.