Thanks everyone for feedback.
This could be something weird with the xen network-interface bridging. This problematic server-system is the only xen guest that shares *both* network cards on the machine.
I asked my upstream ISP to check things from their side.
I hope I will soon get a ssh account on some client where the error is reproducible. Then I could start testing.
- Jussi