Hm, mein Fehler - im Wiki hab ich natürlich nicht nachgelesen ...
Aber seit ich meine Konfig wie beschrieben angepasst habe funktioniert der Logrotate sauber und ich habe auch noch keine Probleme bei einem Neustart gehabt !?!
Nachdem ich den Wiki Artikel jetzt gelesen habe 
Habe ich folgende Anpassung vorgenommen
root@mail:~# cat /etc/init/rsyslog.conf
# rsyslog - system logging daemon
#
# rsyslog is an enhanced multi-threaded replacement for the traditional
# syslog daemon, logging messages from applications
description "system logging daemon"
start on filesystem
#start on startup
stop on runlevel [06]
#expect fork
respawn
script
. /etc/default/rsyslog
exec rsyslogd $RSYSLOGD_OPTIONS
end script
root@mail:~# cat /etc/default/rsyslog
# Options for rsyslogd
# -m 0 disables 'MARK' messages (deprecated, only used in compat mode < 3)
# -r enables logging from remote machines (deprecated, only used in compat mode < 3)
# -x disables DNS lookups on messages received with -r
# -c compatibility mode
# See rsyslogd(8) for more details
RSYSLOGD_OPTIONS="-c4 -n"
Die Option -n bedeutet: Avoid auto-backgrounding, mit diesem Parameter gibt "status rsyslog" dann auch den Dienststatus korrekt zurück. Ich werde die Sache in den nächsten Tagen mal beobachten, aber ich denke das es so funktioniert. Zumindest läuft nach einem Neustart und nach manuellem stop/start des rsyslog alles sauber.
Danke für den Tipp mit dem Wiki, wer lesen kann ist halt klar im Vorteil :-))
Gruß
Andreas