I fixed the problem, but I don't know what caused it.
I noticed that any new images did not have a thumbnail in the attachment manager. Everything displayed as the default "?" thumbnail.
So I rebuilt the thumbnails in "Control panel -> Maintenance". That not only made the thumbnails appear, but also made the image upload process work again. I can now upload images again. It does not look like I'll have to rebuild the thumbnail cache again.
There is something wrong in the source, for sure. I did not find the problem yet. I'll search some more, but without an error and stack trace I'll have a hard time finding the problem.
Just to reply:
Everything is custom about my site. Custom hacks, plugins,... you name it.
This post caused all the trouble, but it works now.