According to the iPhone developer Jonathan Zdziarski "all of the personal information that was sitting on [his iPhone] prior to the erase or restore is still left sitting in the unallocated blocks of the iPhone's NAND memory." In other words doing a Restore operation through iTunes will not actually fully delete all the data on the iPhone. What's needed is a low-level format of the NAND, but there doesn't seem to be a readily available means for doing this.
With the 3G iPhone presumably about to drop it seems safe to assume a lot of second-hand iPhones are about to become available on eBay, etc. It would be nice if there were some fully reliable way to ensure that all personal data is expunged from the device. The original information is on Zdziarski's blog.
Update: Just to be clear, the data was recovered using forensics software. Average users who buy refurbished iPhones will not have easy access to the previous userss data, though it will still be there waiting to be recovered by anyone with the proper expertise.