Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is there some constructive way to enumerate the possibilities? If the polytope has $k$ vertices, is there some nottoohorrible upper bound on the number of possibilities?

By Gale duality, the possible arrangements of $16$ points in $\mathbb{R}^9$ are in bijection with the arrangements of $16$ points in $\mathbb{R}^5$. See Ziegler, Lectures on Polytopes, Chapter 6 for background on this. In particular, Corollary 6.20 in Ziegler tells you which configurations of 16 points in $\mathbb{R}^5$ are Gale dual to vertices of polytopes. I don't think you are going to find a listing of all possible combinatorial types of $16$ points in $\mathbb{R}^5$ anywhere. The Oriented Matroid database is collecting this sort of data but, as you can see, the number of isomorphism classes of even 9 points in $\mathbb{R}^5$ is already listed as "unknown". In short, there are tools to analyze this sort of thing, namely Gale duality and oriented matroids, but a complete list is likely to be out of reach. 


It is very difficult to enumerate the combinatorial types of ddimensional polytopes with n=d+r vertices when d>3 or when r>3. It is also difficult to give good asymptotic upper bounds. Let me mention some results and links. 1) There is a well developed theory largely developed by Tutte to determine the number of 3polytopes with n vertices, as well as of special type of such polytopes. 2) In dimension 3 Steinitz's theorem asserts that a graph G is the graph of a 3polytope iff it is 3connexted and planar and this happend iff G is the graph of a polyhedral complex realizing S^2. 3) For dpolytopes with d+3 vertices a complete enumeration, as well as enumeration of simplicial polytopes was found by Perles based on Galetransform. Also in this case all simplicial [polyhedral] spheres come from polytopes. 4) When d>3 and when r>3 there are much more spheres than polytopes. Upper bounds for the numbers of simplicial polytopes, and general polytopes were obtained by Goodman and Pollack (see Stanleys comment above) and Alon respectively. These upper bounds are based on the MilnorThom theorem. (Probably they are quite horrible.) Much much huger lower bounds for the number of triangulations of (d1)dimensional spheres were obtained by me (d>4) and Pfeifle and Ziegler (d=4). The asymptotic behavior of (log) the number of triangulations of 3spheres (and manifolds) with n vertices is still unknown. 5) The best known lower bounds for the number of polytopes for general d and n were obtained by Shemer based on a "sewing construction" discovered by him. (A closely related construction was discovered around the same time by Barnette.) 6) Bruckner (1909) enumerated all simplicial 4polytopes with 8 vertices (this is the first case not falling under 2) and 3) ) and his work was completed by Grunbaum and Sridhatan. There are 37 combinatorial types and additional 2 triangulations of $S^3$ which dont come from polytopes. 7) Altshuler and Steinberg enumerated all 4polytopes with 8 vertices  there are 1294 (and all of them are rational) and all 3dimensional polyhedral spheres with 8 vertices which are not polytopal  there are 42 of those. 8) Altshuler and Steinberg also enumerated simplicial 3spheres and manifolds with 9 vertices. There are 1297 combinatorial types of 3manifolds with 9 vertices; all of them are spheres except one. Of those Altshuler and Steinberg showed that 1090 are polytopal, 142 are nonpolytopal and the resy were not decided by them 9) Frank Lutz found that there are precisely 249015 triangulated 3manifolds with 10 vertices. 247882 of those are spheres. Lutz and Sulanke showed that there are 172 638 650 triangulated 3,anifolds with 11 vertices. (Again, most of them are spheres.) 10) It is known that the number of simplicial dpolytopes with n facets (equivalently the number of simple dpolytopes with n vertices) and even the number of shellable triangulations of the (d1)spheres is only exponential in n namely it is bounded from above by $C_d^n$. This is not known to be either true or false for triangulated spheres. (It looks that understanding the case asked by Igor and even giving good estimates is beyond reach now. But this may depend on the precise motivation.) 


I've got some information about a lower bound. We know how many binary codes there are of length 5 on n words  http://oeis.org/A034190. Each corresponds to a subset of the vertices of a cube and thus a convex polytope. For length 5 with 16 words we get 169112, and a total of 1,226,525 up to symmetry. I've computed the flag vectors for all such polytopes in dimension 5  http://arxiv.org/abs/1011.4269. Including polars I get 688,298 flag vectors. (I did this for a good reason.) From this calculation I can conclude that in dimension 5 with up to 32 vertices there are at least 344,149 such polytopes that are combinatorially distinct. 

