The problem with your p(n) and q(n) curves are that they measure the probability of at least one match. What we really want to measure is the expected number of matches since due to a difficulty setting having more than one match is important. This is what gives a relationship of number of hashes/second * amount of RAM. Even if we only increase the hashes/second by a factor of two we still get twice as many matches giving linear scaling in exactly the same way as just using whatever birthdayhash algorithm you choose by itself.
Actually I've given it some more thought, and now I'm finding this very convincing.
Let's say 365 possible birthdays and a CPU can generate 10 per second, and process a maximum of 10 per second into memory.
Add a GPU that can generate 100 per second, reduce the search space by 90%, discard 90 of the birthdays that aren't in the smaller search space, and send the 10 to the CPU to process into a search space of 36 days.
So the q(n) might only be half as effective as the p(n), but hashing can be added *infinity and we're getting linear scaling.
We need to prevent easy reduction of the search space.