Symlinks.
> Softlinks (you probably mean symlinks?) are not a good general solution because not all servers (especially shared hostings) do support them at all.
Solution:
> Separate folders for original, resize and thumbs is not bad either.
OK, it's not a general solution for the Image Search Engine indexing, but nice.
A general final solution would be well, also extra folder for prev/next and random. That will be a bit much.