Tak nakonec mě Jano Vongrej nakopl správným směrem, posílám shrnutí pro archiv.
Problém byl nakonec v unit souboru `firewalld.service`, kde původně stoji `Type=dbus`. Při tomhle nastavení SystemD čeká, až mu FirewallD po dbus-u oznámí, že naběhl. Protože dbus pod OpenVZ tak nějak nefunguje, `systemctl start firewalld` po čase skončil neúspěšně timeoutem.
Změnou unit souboru na `Type=simple` byl problém vyřešen a FirewallD běží jak má.
Pro mě ponaučení pro příště popsat problém kompletně (timeout), ne jenom "nefunguje s touhle chybou" :)
Díky Janovi za ochotu a pomoc. Khardix