Yes, it is supposed to be in the upload folder, since the webserver user should always have 'write' privileges there, but may not on the plugins folder. Seemed like the best place to put it anyway...
Are your wordpress folder and uploads folder on the same filesystem? It almost seems like there is some trouble with files in the uploads folder being inaccessible (perhaps if they are on a network share), since you are having trouble with some images during the bulk process as well. I would check with your host to find out (if you don't already know).
Oh, and you asked why it has no trouble with files wordpress created, but trouble with the originals, and I would suspect it is a simple matter of size. The smaller files (resizes) are able to be read quicker. If we take this into account with the ewww.tmp file then we have to consider how many images you are processing at once. On my test site with around 550 images, I get a .tmp file of about 450k, which would be closer in size to some of your original images (or perhaps even larger).
Last thought for now regarding 'slowing things down' is that many users already have trouble getting a bulk operation to finish due to timeouts and such, so I don't imagine this being a good solution. Especially on shared hosting, long running processes are prone to getting killed by the server. Your issues seem to be purely with the actual read from disk, and I'm honestly a little surprised that it would actually timeout on this portion. Perhaps it is a memory issue, where the file is too large to be read into memory due to some limitations of your host?