I was fighting this same issue today and came up with what I believe is a solution. I run CentOS servers and my solution focuses on that distro.

#1 - update to the latest version of syslog
create /etc/yum.repos.d/rsyslog.repo and place the following into it

[rsyslog_v7]

name=Adiscon CentOS-$releasever - local packages for $basearch

baseurl=http://rpms.adiscon.com/v7-stable/epel-$releasever/$basearch

enabled=1

gpgcheck=0

gpgkey=http://rpms.adiscon.com/RPM-GPG-KEY-Adiscon

protect=1

Move your existing /etc/rsyslog.conf file to another directory prior to upgrade. This will allow the installer to create a new conf file for you. You can copy/paste your custom settings into the new file post upgrade.

Execute the command 'yum update rsyslog' to update rsyslog.

#2
The following code shuld be placed before the "*.info;mail.none;authpriv.none;cron.none /var/log/messages" entry. Be sure you replace <ServerName> in the example below with the name of your central logging server

# Log each remote host into it's own directory and then discard remote server logs:

$template RemoteHost,"/var/log/remote-hosts/%HOSTNAME%/%HOSTNAME%-%$YEAR%%$MONTH%%$DAY%.log"

if ($hostname != '<ServerName>') then ?RemoteHost

& ~

From my research on this, position in the file is critical, you must capture the remote server logs, place them into the dedicated location and discard them when done prior to the *.info entry.

I hope this helps. I am not guaranteeing that there will be no issues with this setup. As far as I can tell, logging to the local server is working normally and remote hosts all get their own directory and a file with the date string (properly sorting) embedded.

You'll want to check out the link below to make sure you are compressing the old log files.
http://wiki.rsyslog.com/index.php/DailyLogRotation