iPhone 3GS charging, but sparsely or never recognized by PC

I have an iPhone 3GS that isn't damaged externally. It didn't fall down, no water damage, nothing..

When I plug in the USB cable for a PC connection it starts charging, but isn't always recognized by Windows (or Linux or OS X). On some PCs it is _never_ recognized (e.g. a PC with Intel P55 USB, 2009 iMAC, 2010 MBP, ..), on other PCs it is _usually_ recognized. If it gets recognized, the sync works just as it should. No transfer problems or connection aborts or something like that.

The problem is now, that I can't even restore the firmware. When I try, the iPhone reboots and when it shows that upgrade progress bar on the screen it isn't available via USB any longer. After some timeout it just reboots into recovery mode without firmware upgrade and iTunes fails with 1602 or 1611. Same happens when I try restore from recovery or DFU. On my AMD notebook it shows "Unknown device" messages when in the progress bar mode. On linux it says something like device enum failed in this state.

I think this is a hardware related issue. Has anyone experienced this strange issue before?