The bug is similar to 22750 but according to developer's request is filed here as separate issue.

It's easily reproducible in following configuration:

Server: most recent Bitnami Appliance (Ubuntu-based), jenkins.war manually upgraded to 1.577
Slaves: 1 'cloud' in-demand slave, managed by virtualbox plugin, Ubuntu 14.04 LTS x86_64 with OS 'native' LAMP stack.
SCM: git in local network on a separate server, accessible by ssh & git protocols
Job: default 'free-style job', with Build Trigger set to 'Poll SCM' once per hour (doesn't matter fixed or randomized), tied by node name to the particular slave (in-demand cloud VB slave)

Manual job triggering brings the node online and after the configured delay (3 min in my case) jenkins proceeds with the rest of the job. Changes in SCM cannot trigger the build, git polling log shows the message: "We need to schedule a new build to get a workspace, but deferring in the hope that one will become available soon (all_suitable_nodes_are_offline)".

This is not just a bug, it's a sort of logical trap. Jenkins has to make the decision to power up slave node(s) based on the results of SCM Polling, but unable to do that, because the very SCM Polling can be done only on the node(s) which are currently offline.