Could you check the irq count and ethtool -S eth0 as well ?

Here you go: http://pastebin.com/acabFBHv

Does the laptop also include a different operating system ?

Yes, Windows 7.

quoted

I haven't used that interface for quite some time, a year at most. I
keep up to date with the stable kernels, so a version change broke it,
but I'm not sure which. Would it be the best course of action if I
tried some older versions?

Yes, please do.

There has been no specific change in this timeframe for the chipset you
use (RTL_GIGA_MAC_VER_25). The problem may have been unnoticed for a
rather long time. :o/

I booted into an old kernel I found in the Debian repository: Linux
wicklow 3.2.0-4-686-pae #1 SMP Debian 3.2.53-2 i686 GNU/Linux

And the same issue happened. Queue times out, no packets are received
on the other end.

Could it be that this regression ended up in this long-term supported
kernel? Or could it be a hardware problem? My Windows laptop's
ethernet definitely works in other places, so could be the cable or
the integrated NIC in the Linux machine...

Best regards,
Jozsef