Identifying Binary Search Trees from their Prufer Sequence If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found that there are A000245 distinct Prufer sequences.
import itertools

def generate_tree(l):
    '''Return the root and a set of edges'''
    if len(l) == 0:
        return None, None
    if len(l) == 1:
        return l[0], set()
    left_root, left_edges = generate_tree([x for x in l if x < l[0]])
    right_root, right_edges = generate_tree([x for x in l if x > l[0]])
    edges = set()
    if left_root is not None:
        edges.add((left_root, l[0]))
        edges.update(left_edges)
    if right_root is not None:
        edges.add((l[0], right_root))
        edges.update(right_edges)
    return l[0], edges

def pruffer_sequence(edge_set):
    degrees = {}
    for v1, v2 in edge_set:
        degrees[v1] = degrees.get(v1, 0) + 1
        degrees[v2] = degrees.get(v2, 0) + 1
    r = []
    while len(edge_set) > 1:
        smallest_leaf = min([v for v in degrees.keys() if degrees[v] == 1])
        degrees[smallest_leaf] -= 1
        for e in edge_set:
            if smallest_leaf in e:
                edge_set = edge_set - {e}
                neighbor = [v for v in e if v != smallest_leaf][0]
                degrees[neighbor] -= 1
                r.append(neighbor)
                break
    return r

for number_of_vertices in range(2, 10):
    R = set()
    for l in itertools.permutations(range(number_of_vertices)):
        root, edge_set = generate_tree(l)
        R.add( tuple( pruffer_sequence(edge_set) ))
    print number_of_vertices, len(R)

Is there some way to characterize a BST by its Prufer sequence without first calculating its tree?
 A: Is there a reason you chose to take the BST of the permutations? There are multiple ways to uniquely represent a permutation as a tree, where you would end up with $n!$ different Prufer sequences. Categorizing such sequences might be more interesting.
But in any case, I couldn't find a way to enumerate without iterating all the $n!$ permutations. I tried to find a bijection between Prufer sequences and something counted by the difference of Catalan numbers $C_n-C_{n-1}$, but to no avail.  I was however, able to speed up your code.
Given two permutations $p_1, p_2 \in S_n$ 
$$ \text{Prufer}(p_1) \;\;\;= \;\;\; \text{Prufer}(p_2) \\
\Longleftrightarrow  \\
\text{Tree}(p_1) \;\;\; = \;\;\; \text{Tree}(p_2) \\
 \Longleftrightarrow \\
\text{Edges}(\text{BST}(p_1)) \;\;\; = \;\;\; \text{Edges}(\text{BST}(p_2)) \\
$$
So you only need to find the Prufer sequence when you come across a new edge set. Also, if you actually construct the BST, you can find the Prufer sequence in linear time. Here is my python code (takes 6 seconds rather than 18).
