Just took a look at this question and was struck by the lovely list of related questions:
Should we add this title to the low quality posts filter?
Or have some logic that checks for how similar a title is to other titles (and how many of them) and for high values of similarity and duplication add to the low quality score?
kiamlaluno in his comment to his answer suggests that we could use the title Levenshtein distance as a measure for the similarity of a title to existing titles - I believe this would work well - if a title scores high (is very similar) to (arbitrary number here) other titles, that would be a flag for low quality.
With the above, instead of "a question with that title already exists" we could have "several questions with very similar titles already exist; please use a more descriptive title".