Looking at a debug patch with a tripleo run, the instance that fails the heat stack create with the 404 fails to schedule:

http://logs.openstack.org/60/428360/2/experimental/gate-tripleo-ci-centos-7-nonha-multinode/7a6e5bc/logs/subnode-2/var/log/nova/nova-conductor.txt.gz#_2017-02-03_05_17_35_826

2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager [req-5e120dea-89b0-4cf7-a7cc-d7893234aea2 - - - - -] Failed to schedule instances
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager Traceback (most recent call last):
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/conductor/manager.py", line 866, in schedule_and_build_instances
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     request_specs[0].to_legacy_filter_properties_dict())
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/conductor/manager.py", line 597, in _schedule_instances
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     hosts = self.scheduler_client.select_destinations(context, spec_obj)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/utils.py", line 371, in wrapped
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return func(*args, **kwargs)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/client/__init__.py", line 51, in select_destinations
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return self.queryclient.select_destinations(context, spec_obj)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/client/__init__.py", line 37, in __run_method
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return getattr(self.instance, __name)(*args, **kwargs)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/client/query.py", line 32, in select_destinations
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return self.scheduler_rpcapi.select_destinations(context, spec_obj)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/rpcapi.py", line 129, in select_destinations
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return cctxt.call(ctxt, 'select_destinations', **msg_args)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/oslo_messaging/rpc/client.py", line 169, in call
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     retry=self.retry)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/oslo_messaging/transport.py", line 97, in _send
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     timeout=timeout, retry=retry)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/oslo_messaging/_drivers/amqpdriver.py", line 458, in send
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     retry=retry)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/oslo_messaging/_drivers/amqpdriver.py", line 449, in _send
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     raise result
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager NoValidHost_Remote: No valid host was found. There are not enough hosts available.
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager Traceback (most recent call last):
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/oslo_messaging/rpc/server.py", line 218, in inner
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     return func(*args, **kwargs)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/manager.py", line 98, in select_destinations
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     dests = self.driver.select_destinations(ctxt, spec_obj)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager   File "/usr/lib/python2.7/site-packages/nova/scheduler/filter_scheduler.py", line 79, in select_destinations
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager     raise exception.NoValidHost(reason=reason)
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager NoValidHost: No valid host was found. There are not enough hosts available.
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 
2017-02-03 05:17:35.826 43546 ERROR nova.conductor.manager 

That should put it in the cell0 database and the _get_instance() method in the compute API should pull it out of there.