So, I have to delete about 500,000 custom records (safe to do so). Would you do a mass update or Map/Reduce?

I wrote very simple Mass Update script for deleting any type of record : just put record. delete({type, id}) in the mass update function. NetSuite invokes M/U script with record instance, so you have type and id.. Later create deployments for each type of records you want to provide mass "delete". I prefer mass update just because you can PREVIEW what's going to be deleted

We use both. Personally, I'd try mass update in the first instance if you can split it into smaller chunks and run multiple jobs. Map/reduce if you want to delete all at once.