OK, after a more or less sleepless night and hours of studying protocols, I found the devil! And since I hate it when threats are closed without solution here comes the solution for this one:
The injection occurred through the plugin "Effects for NGGallery". I recommend to immediately delete this plugin with all files in it. The bugger sits in the utmost deepest folder of the plugin. Before I deleted it (don't bother deactivating it - who knows what that might cause...), I made note of how the injection was built.
9 files are added to the folder wp-content/plugins/effects-for-nextgen-gallery/effects/highslide/lib/themes/default/graphics/outlines
1. 370.php which contains the first crack of wp salt and attacks the storage of the secret key. And it does probably lots of other things too. Like infecting my config file with some additional keys.
2. ee7b.php does about the same as the above. Lots of encrypted stuff starting with a salt attack.
3. bi is an empty file
4. csi converts ip addresses into numbers
5. cnf is an encrypted config file and I guess the guy has access to the complete wp by now.
6. lb is the link library so actually searching for one of the urls in this list, easily copied from the infected site's source code, on the cpanel's file manager should reveal the location of this file.
7.lock is an empty file
8. rlf is the click counter
9. skwd are the site keywords, basically a list of all words you can imagine, very long.
If your site got infected read this: After removing the folder with the plugin you need to go to your config file and change the secret keys. This is essential otherwise you might get it back again. When you get to the config file you will find a website address where you can obtain new secret keys. It's as simple as copy/paste but important to do it. The hacker has modified this file by adding additional keys, thus letting a back door open for future attacks.
I'm not 100% sure if it was the effects for nggallery but it was the oldes plugin on the site, last updated 500+ days ago which made it suspicious to me.
As a last note, the plugin was installed on only one of the two sites, but the link list showed in both sites, so if you run multiple sites on one account, better change the secret key there too.