Dealing with Selenium tests that fail occasionally during automated deployment

I don't like either of the suggestions that you mention, but I admit to having used them occasionally. The best thing to do is to make sure that when there is a seemingly "random" failure to do everything you can to get all of the data about why it really failed. Was it an environment issue? Did some other process on the machine interfere with the tests? Was it a timing issue that only appears when the site loads excruciatingly slow, or blazing fast?

One thing that you might try is soak testing your automated tests. Run each one 100+ times on the same build and same environment (so you can rule those out as potential failure points) and find the ones that fail occasionally. See if they fail in the same place or in different places. Generally, when you go through this exercise you'll find some tests that really are a little bit flaky and you can remove them from the daily run until they are fixed. You could even include a soak as a check-in criteria for any automated test case.

Another useful thing I have found that helped me get to the bottom of some of the seemingly random failures was taking screenshots on failure. Often you can see that other windows or dialogs were popped up causing the browsers not to be able to be in the forefront, etc.

Of the two, I would prefer to rerun test failures, or rather, on test failure, retry the tests.

If you accept a certain number of test failures, then you get into problems about which tests are allowed to fail. You would have to have two sets of tests, some which are allowed to fail, some which are not.

For rerunning, I'm no expert on testing with NUnit, but you could have the tests themselves manage the retry. In JUnit, you can introduce a rule so that if a test fails, it would retry a maximum of 3 times. This would probably avoid most of the problems you're having. I don't know how to do this in NUnit, but see my answer to How to Re-run failed JUnit tests immediately?. This will give you the general idea.