I still don't know what exactly went wrong, but after I removed all of the OpenCV stuff and re-installed a fresh v4.1, it worked. So even though I checked all lib-files, there must have been something wrong with the linked libs (Pointing to different versions?! Links not working?!, etc.)
Thanks @SGaist, your answer made me remove everthing and try the OCV version that is provided by Ubuntu 18.04. I got 3.X.X from there... After I removed this version again (because I want a newer one) and installed 4.1 from OCV page, it worked :-)