hmmm... after a little more searching I would go back to your hoster...
You are getting an 'Out of Memory' message and not the more typical 'Allowed memory size of X bytes exhausted'...
Some quick searching (Google Is Your Friend - GIYF) - two possibilities seem to be an Apache level memory limit or physical memory.
Look for RLimitMEM in http.config (apache conf file) - I'm thinking this is more likely.
Either an unreasonably low limit - or you are running too many other parallel processes.
Look at Apache's error log for errors/crashes - as it wouldn't have survived the encounter:
'zend_mm_heap corrupted' as an example.
Virtual servers should have sufficient virtual memory to handle far more requests that the physical memory on the machine - especially in a shared hosting environment... though wouldn't surprise me with some of the hosts I have run into.
You didn't say how large the photos are - but looking at the bytes allocated and requested - they aren't that large...
"(allocated 3932160) (tried to allocate 786432 bytes)" - only 3.9M allocated - and only requesting 786K (0.786M)