I'm on my fifth iPhone 3G (long story, usually dust under the screen) ...
Three of the four iPhones I took in to the Apple Store were jailbroken. I made no effort to hide the Cydia icon, etc - I just disabled any custom themes I had installed. No problem.
I've had to return my iPod twice (again, dust under the screen) and I never bothered restoring it, either. 😎
I mean, seriously - what's the worst they can do? Deny service? Great. If they did that, I'd just go downstairs, connect the iPhone to one of the iMacs they've got on display, and restore it. Voila! No more jailbreak. 🙄