Finally solved my problem. For everyone whos interested, heres the answer:
It seems as if Android only preloads the VideoViews video, when the view is part of an XML-Layout, which is also currently active. So if you want to preload a video, make the videoview part of your xml and do not create a videoview-object with the constructor, as I've done it. Then it should work! :D