I was more concerned with finding a cheap mechanism for dealing with dups when they occur as I think any mechanism for preventing them is doomed to fail and would be prohibitively expensive.

I think the main reason unintentional dups occur (from my own personal experience) is that I click submit, and then either a) my connection drops and when it is restored I am not sure if the submit was transmitted before the drop. or b) I click, and immediatly notice a typo and hit stop, edit then submit again. From my perspective as I haven't seen the screen refresh, it looks as if I was in time, but there is a window in which this can cause a dup. In this case, the MD5 wouldn't work as the text would have changed.

As for String::Approx. Have you timed it? Quick it ain't. Even if you only used it to compare against the previous post by the submitting author, it is going to chew lots of cycles (as you indicated:). If you were trying to catch Anonymonk posts, the most frequent offenders I think, then you would have to cross check against all Anonymonk posts for say the last 10 or 15 minutes which at busy times would bring the server to its knees.