Found it!
I was using Blazers XWISP wrapper. His wrapper was disconnecting (intentionally) every Renrem telnet session after just one command. Reading through his comments it seems this was the orginal behaviour of brenbot aswell (disconnect after every command).
But with the current brenbot multiple commands are sent through the same telnet session causing more than one message to be lost. This is for example the case with !kick. Where you first get a msg command and then a kick command. The kick command would be lost because the XWISP wrapper had disconnected by then.
So the fix is to comment out the following lines in sub macrem_input. (Thats line 307 of my modified xwisp.pl)
$_[KERNEL]->yield("shutdown"); # Then disconnect the remote admin
delete $users->{$session_id}; # Cleanup session vars;
Sorry for blaming brenbot for doing this