I think a mining process that made use of stochastic sampling of a large data set would meet the requirements you have laid out. The blockchain even provides a great data set for this. For example, let's say each nonce requires you to randomly sample the blockchain to pick out a few bytes. Since you use many nonces while mining and couldn't predict which data you would need from the block chain, you would basically need to have the whole block chain (any publicly agreed upon data set, really) available while mining. The solution can then be verified with a small sample of that data set and some proof that the data is in the set. When using the blockchain example, you would probably need a chain of block headers and a merkle branch for the transaction data selected.
Another way to do this would be to use a large random merkle tree. Let's say someone created a merkle tree of 2^31 random 32 byte values. When taking into account that the merkle branches have to be stored as well, this is (1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytes, or (2^32-1)*32 ~= 137.4 GB of data in all. This data is very publicly available for anyone who really wanted to download it and verify the merkle root. The merkle root would be made known as the mining merkle root, and it is a well known and agreed upon constant. Mining involves sampling this random merkle tree and hashing, and with finding a successful solution, the merkle tree branch is provided, proving that the data that was sampled is actually in the publicly agreed upon merkle tree.
In this scheme, it takes ~137.4 GB of memory to mine, but only ~1 kB of data to verify a solution against the publicly agreed upon mining merkle root.
And the numbers could obviously be tweaked here to allow people to mine without giving up 137.4 GB of their harddrive. A balance would have to be reached.
I actually like this way better, now that I think about it, because it doesn't have the side effect that mining can take longer as the block chain grows. You could probably even snapshot the bitcoin block chain and use that as a pubicly verifiable data set. But the block chain method essentially forces nodes to be full nodes as well, which is interesting, so it's a tradeoff.
Edit: With a quick search, I turned up this paper that solves essentially the same problem with a different stochastic sampling method involving the birthday paradox. Their solution is interesting because it involves building your own large data set each time. But this may not actually be a good thing, as it discourages re-building of blocks when new transactions come in.
http://www.hashcash.org/papers/momentum.pdf
A relevant bitcointalk discussion on the Momentum algorithm:
https://bitcointalk.org/index.php?topic=313479.0
I think it's funny how the 'momentum' aspect (not being able to update merkle after it is first created) is touted as the defining characteristic of the algorithm, even though it's actually a pretty significant downside, delaying confirmation of all transactions by 1 block. It may also exacerbate the problem where miners don't want to mine large blocks because they take long to propagate. i.e. It may be more profitable to continue mining with your tiny block even after you have heard about a new block on the network because the momentum you already have makes it easier. I think the fact that bitcoin's PoW algorithm does not have any momentum is actually a great feature, allowing for transactions to get confirmed quickly.
Using an unchanging data set, like in the solution I provided above, provides the desired asymmetric memory requirements in working/verifying work, while also avoiding the problem of momentum.
