Cannot re-install OS X Lion after trying to format Macbook Pro
When you're booted from the CD and looking at Disk Utility, you need to use the Erase tab, not the Partition tab.  The EFI and Recovery partitions are hidden from view, so even if you delete all the partitions on the disk, it still won't delete that one.

If that still doesn't work, then you can open up a terminal window, and issue the following command:

diskutil zeroDisk /dev/disk0


That will zero out your entire hard drive, including all your partition tables.  But it could take 2-3 hours depending how fast your hard drive is.  Once it's done, you can create a new partition and install the OS.

If course, if you're really pedantic like me, you'd remove all media from the optical drive and USB ports, zero the hard drive, power off, zap the PRAM, reset the SMC, and then boot from Internet Recovery to do the OS install.  That's factory fresh right there, my friend.  The only thing it won't have after all that is the new computer smell.