Any time you throw away hashes because they fall outside of your memory range you move the computational complexity from the p(n) curve to the q(n) curve in my white paper. You save on memory but the cost is far greater. Memory and CPU power must always be paired proportionally or you will have idle memory or waisted CPU cycles.
I don't wanna pollute your thread with many small replies. If you answer what hashing-power we're looking at in mhashes/s I could make a more thorough reply with numbers. Also, is 32 bit output for birthdayhash right? That would only take storing 77000 entries for 50% chance of finding a collision.
My Scrypt-like hashing function runs on a single core at about 1 k/hash with relatively few optimizations.