Q:

Why is syslogd not reporting messages to remote server during and just after the boot?

I configured rsyslog to send logs to a central logging server like this:
*.* @@192.168.1.20
$ActionExecOnlyWhenPreviousIsSuspended on
& @@192.168.1.21
& /var/log/failover
$ActionExecOnlyWhenPreviousIsSuspended off

It works well, except when machine is booting. When the virtual machine starts and approximately twenty seconds after the machine starts, no messages are sent to 192.168.1.20 or 192.168.1.21. However, /var/log/failover contains all those “lost” messages.
As a test, I started the machine and entered by hand:
$ logger 1
$ logger 2
$ logger 3
...

The first central logging server contains just:
Nov 28 13:57:40 demo arsene: 10

The second logging server contains no messages from the demo machine.
Finally, var/log/failover on demo machine contains:
Nov 28 13:57:10 demo rsyslogd: [origin software="rsyslogd" swVersion="7.4.4" x-pid="361" x-info="http://www.rsyslog.com"] start
Nov 28 13:57:10 demo rsyslogd: rsyslogd's groupid changed to 104
Nov 28 13:57:10 demo rsyslogd: rsyslogd's userid changed to 101
... # more than a hundred usual messages from the kernel
Nov 28 13:57:20 demo kernel: [   12.127981] random: nonblocking pool is initialized
Nov 28 13:57:21 demo arsene: 1
Nov 28 13:57:22 demo arsene: 2
Nov 28 13:57:23 demo arsene: 3
Nov 28 13:57:25 demo arsene: 4
Nov 28 13:57:27 demo arsene: 5
Nov 28 13:57:28 demo arsene: 6
Nov 28 13:57:30 demo arsene: 7
Nov 28 13:57:32 demo arsene: 8
Nov 28 13:57:37 demo arsene: 9

I encounter this issue for both Ubuntu and Debian virtual machines.
Additional notes:

The network connectivity looks fine. If I try ping 192.168.1.20 and curl google.com during the period where the log messages are not sent to the log server, both ping and curl succeed.
Disabling the firewall of the logging server has no effect.
Running tcpdump shows that nothing is being sent to the log server during the twenty seconds period.
Other Ubuntu machines on the network (which were deployed using a very different approach) report their logs to the logging server fine, including during the boot.
By comparing the faulty machines to the correct ones, I noticed a version mismatch (7 vs. 8) for rsyslogd. Upgrading rsyslogd on faulty machines to version 8.14.0 haven't fixed the issue, but now I see the following message a bit after the log reporting starts working:
Nov 29 02:18:39 demo rsyslogd-2359: action 'action 11' resumed (module 'builtin:omfwd') [v8.14.0 try http://www.rsyslog.com/e/2359 ]

diff shows that /etc/rsyslog.conf and /etc/rsyslog.d/*.conf files are exactly the same between the new faulty machines and the old working ones.
A apt-get update, apt-get upgrade and even apt-get dist-upgrade haven't fixed the problem.

A:

As @ThomasDickey said, networking may not be completely started when userland programs start to run. Many enterprise ethernet switches don't accept packets for a number of seconds after an interface comes up, as they try to negotiate spanning tree settings.
rsyslog has an actionresumeinterval setting that is 30 seconds by default. If you set it to a smaller value before any directives that use TCP connections, that will increase the retry rate, and the connections ought to get completed more quickly.
There are also additional options you can set to ensure that early messages which are  not sent immediately get delivered as soon as the connection is ready. For instance, you can use the options similar to:
$ActionResumeInterval 5
$ActionQueueType disk
$WorkDirectory /var/spool/rsyslog
$ActionQueueFilename actionRq
$ActionQueueMaxDiskSpace 1m
$ActionQueueSize 4000
$ActionQueueTimeoutEnqueue    0
$ActionResumeRetryCount -1

