CentOS - Jun 2016 - Centos 7 boot hanging unless systemd.log_target=console is used

I have multiple VMs that are hanging on boot. Sometimes they'll boot
fine after 5 mins and other times it'll take over an hour. The problem
seems to be related to journald but I'd like to figure out how I can
get more information.
The VMs are running CentOS 7.1.1503. systemd and journald are both
version 208. We are reluctant to upgrade to the newest CentOS because
we found that journal-gatewayd is broken on boxes that have been
upgraded.

If I add the kernel parameter systemd.log_target=console then they
boot up fine without hanging at all. I can't seem to get into the
debug shell (Ctrl+Alt+F9) while the system is hanging after enabling
debug-shell. Adding systemd.log_level=debug without
systemd.log_target=console seems to make the problem worse and causes
a hang of over an hour. I tried deleting /var/log/journal but that
didn't help and I ran fsck on the root drive with no errors. I also
tried masking systemd-udev-settle but that didn't help either.

While the system is hanging the last console output is "Welcome to
CentOS Linux 7 (Core)!".

Here's the output from dmesg without "quiet" kernel parameter and
without "systemd.log_level=debug": http://gobin.io/zScc

systemd-analyze blame doesn't seem to help either (top 3):
10.451s nginx.service
 7.149s network.service
 2.178s etcd.service

What else can I do to debug this?

Thanks!