A restore basically does a "quick format" on all partitions before reloading the OS. Manually selecting the "Erase All Content and Settings" option does a complete wipe on the User partition only, but it physically zeros out the flash memory. I can see this being useful for privacy reasons but I don't see how Apple's software could detect leftover files once a format (even a quick one) has been done. It's likely the person you're talking about either did an upgrade (instead of a restore) or simply restored from a jailbroken backup which put certain custom settings back that wouldn't exist on a non-jailbroken device.
Speaking from personal experience, I have gotten many (and I mean a LOT) of iPhone replacements at several different Apple stores and have always simply restored before taking it in (and setting it up as a new phone of course). Not once have I been caught and/or questioned about having a previously jailbroken device.
Hmm...perhaps they used a recovery tool that would be able to read the files despite the "quick format". But yeah, looks like we're on the same page and perhaps my solution is a bit extreme...but it's the best way to be 100% in my book.