Having a read through this, somewhat interesting, but would literally be like trying to find a needle in a haystack.
That means that it's not impossible.
It depends on how difficult Satoshi wanted it to be.
He could have generated a random private key and then given clues on how to solve it, without having to create a custom private key, just my 2 cents.
Yes, could be. With different difficulty levels so that not one person can solve all keys. That would allow him to distribute the coins.