The NEW_YOU_QUEST_PATTERN in src/net/sourceforge/kolmafia/persistence/QuestDatabase.java only matches on "encounters with a ", while some monsters (e.g. undead elbow macaroni) will have "encounters with an ".
Oh, I guess there's one more possibility. Today I got "Sharpening the saw! Looks like you've cast Sing during 0 of the required 8 encounters with the man with the red buttons!".