They learned the phrase from Dumbledore when they gave him the map. The fact that they don't remember the map but imperfectly remember the phrase does support the "poorly done obviation" hypothesis. (either because the obliviator missed removing the phrase or the obliviator intended for them to keep the phrase but accidentally messed it up)

(or, less likely, 'Deligitor Prodi' would not have worked for the twins and the obliviator intentionally altered it so that it would)

A few moments later, Fred and George were handing over the Map to the Headmaster, wincing only slightly at the sacrilege of giving their precious piece of the Hogwarts security system to the person who actually owned it, and the old wizard was frowning at the apparent blankness.

"You've got to say," they explained, "I solemnly swear that I am up to no good -"

"I decline to lie," said the old wizard. He held the Map high and bellowed, "Hear me, Hogwarts! Deligitor prodi!" An instant later the Headmaster was wearing the Sorting Hat, which looked scarily right upon his head, as though Dumbledore had always been waiting for a patchwork pointed hat to complete his existence.

(Fred and George immediately memorized this phrase, just in case it would work for somebody besides the Headmaster, and began trying to think of pranks that would involve the Sorting Hat.)