Using a 10.6 DVD should provide with the ability to erase the internal HDD and reinstall
Mac OS X 10.6 Snow Leopard.
With 10.7 it might be more complicated due to the missing installation medium provided by Apple, that one can "only" use Internet Recovery if one doesn't have a 10.7 installer on a DVD or USB flash memory thumb drive.
When I bought 10.7 I created an installer on a USB flash memory thumb drive using
CarbonCopyCloner and I also stored the DMG for future purposes.
Just yesterday I cloned the DMG to another HDD partition to have a bootable installer (I have made an external HDD with ten partitions, four partitions to house all the installers from 10.5 to 10.8m four partitions to house all Mac OS X versions from 10.5 to 10.8 and one partition for mobile backups and one partition for application installers - I did this to have a mobile troubleshooting HDD when visiting clients), and it worked perfectly.
Maybe it is a firmware issue, did your Mac come with
Mac OS X 10.6 Snow Leopard or
Mac OS X 10.7 Lion?