Why can't you just create a pool of databases and truncate all tables after each run ? That should be pretty fast
But yea, DELETEing is faster than creating a DB from template (depends on how much you have to delete, of course). However, templates allow parallelism by giving its test its own database. I ended up doing a mix of both: create a DB if there's not one available, or reuse one if available, always tearing down data.