sometimes they actually are uploaded as I can find them on the media library
You actually do need to check the uploads folder using FTP or whatever file management application your host provides.
There are 3 parts to an image upload:
1. the image is actually uploaded to the relevant uploads folder
2. the image is processed and the various smaller sizes generated.
3. the image is registered in the database
So you can have situations, where steps 1 & 2 complete successfully but step 3 doesn't. In such a situation, the image will not appear in your Media Library. We need to get some idea of exactly where the process is breaking on your site - which is why we need you to confirm whether step 1 was completed even when there's an error message and no new entry in your Media Library.
Does that make sense?