You do need a non hacktivated phone. It does not have to be so clean. In practice, it is often easier for most people to start with a clean legitimately activated phone.
2G phones are a bit trickier with legitimate activation than 3G or 3GS phones. You need to have the original SIM card and it has to have been active on a legitimate plan at some point (can be deactivated now)
3G and 3GS can use any active SIM from a legitimate carrier to activate.