With my grey matter prodded by comments and answers from Mr. Wizard, Ymareth, and ubpdqn, I poked around at the distribution of duplicates, finding that more often than not they were toward the latter parts of the lists. This explains the wild variance in timings for my initial idea similar to ubpdqn's: if "lucky" the short-circuiting helps, but if not, you pay a dear price compared to the efficiency of the vectorized implementation.
With the idea of "rolling the dice" hinted at by Ymareth, I modified my routine to the following.
Module[{tlen = Length[#], dd, ldd, bounds},
bounds =
DeleteDuplicates[Select[{25000, 50000, 100000, 500000, 1000000, tlen}, # <= tlen &]];
Do[If[Length[dd = DeleteDuplicates[#[[1 ;; len]]]] != len, Break[]], {len, bounds}];
If[(ldd = Length[dd]) == tlen, Return[tlen], -Tr[Unitize[#[[1 ;; ldd]] - dd] - 1]]] &[target]
The purely mathematical operation is so quick, the overhead of doing extra work in sniffing at early parts of the list to avoid doing the work on the whole list is surprisingly inconsequential. Lists with early surprises are caught quickly, and those with tail-heavy distribution of duplicates cost only slightly more time. Overall, the average result is at least an order of magnitude faster, often much more, than either my original bare method or using downvalues. I'll post some timing details when I have time.
Thanks to all for comments and replies, I'm quite pleased with the end result!
DeleteDuplicates
for large lists. If so then that could deliver some improvement. $\endgroup$ – Mike Honeychurch Jan 31 '14 at 22:06