Wait.....WHAT?!

The Pink Bean Slayer Medal quest appeared to me after I got to that point in the Time Temple (it might have been that I used my first Marble of Chaos to actually enter the registry NPC room). When the patch first came out, I didn't have that quest in the list. But it appeared not long after, and I believe that was the trigger. Something triggered it, and it definitely wasn't defeating PB. I never attempted to kill it, either. Then I was able to "complete" it like the others.

I have it too:

 Spoiler

In short, I'm saying my theory is you only have to enter the registry room to make it appear. I don't know what else I could have done to trigger it.