Mailings are started but not sent - What is the difference between a scheduled job and "Run it now"?
It seems that there is a bug in CiviCRM 4.7, 4.7.1 and 4.7.2 which causes these symptoms (scheduled mailing stuck at "running" without actually sending, but will send using Execute Now). See here and here. I spent a day trying to find the problem before I came across the bug report, so hopefully this will save others some time looking for a misconfiguration of the mailer.

Edit: The problem has been fixed in 4.7.3.