Edit distance algorithms that depend on alphabet
The answer is certainly yes. Assume for simplicity that the two strings are of equal length $n$. If the "induced" alphabet of each string is also of size $n$, then both strings are permutations, and the problem degenerates to the classical longest increasing subsequence (LIS) problem: it is easy to see that the edit distance between a given permutation $\pi$ and the sorted permutation $1,2,\ldots,n$ is $n-LIS(\pi)$. The LIS problem was studied as early as 1930s by Erdos and Szekeres, and by Robinson. The best algorithms for LIS run in time $O(n \log n)$ or $O(n \log\log n)$, depending on the computation model. Such algorithms were (re)discovered dozens of times (or perhaps hundreds of thousands, considering that the problem makes a good programming exercise), often with various twists. It is easy to find the relevant papers, since most of them cite previous work. The most recent result I am aware of, and a good point to start exploring the references, is the $O(n \log\log LIS(\pi))$ algorithm by Crochemore and Porat:

M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence and application. Information and Computation, 208(9):1054--1059, 2010. http://dx.doi.org/10.1016/j.ic.2010.04.003

The same paper also describes how to interpolate between this extreme case and the general edit distance problem, taking the total number of character matches as a parameter. This is relevant when your "induced" alphabet size is large, but not exactly equal to $n$. For smaller "induced" alphabet sizes (say $n/2$), it is easy to construct examples that are essentially binary over a significant part (say, one half) of each input string, so a large "induced" alphabet over the whole string won't help more than by a constant factor.