How many vertices/edges/faces at most for a convex polyhedron that tiles space? I wonder if this problem has already been examined before: 
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
Intuitively, it seems that the truncated octahedron is best possible for edges (36) as well as for vertices (24)
Its packing is also known as "bitruncated cubic honeycomb".
For faces, we can do better than 14, as there is a polyhedron with 16 faces that can be obtained as follows: Take a truncated tetrahedron and add on each triangular face a small pyramid that is a quarter of a tetrahedron. The tessellation of it is known as the quarter cubic honeycomb, with each small tetrahedron "distributed" among its four neighbors.
Questions:
Are these best possible?
What about the corresponding problem in higher dimensions? 
In $\mathbb R^4$, it looks like the polytope yielded by the equivalent of the "Quarter cubic honeycomb" tiles it. This one, based on the truncated 5-cell has 25 cells, 60 faces, 60 edges, and 25 vertices, and so for cells and vertices, it does again (slightly) better than the 24-cell with its 96 faces, 96 edges, and 24 vertices.
 A: In $\mathbb{R}^3$ this is a famous problem.See this nice reference. (Danzer, Grunbaum, Shepard -- Does every type of polyhedron tile three-space). The best example at the time of the writing had 38 faces (an example of Engel).  For a lattice (periodic) tiling, the problem was solved (I think) by Delone (AKA Delaunay).
A: To supplement Igor's citation of Engel's polyhedron, here it is:
     


The figure above is from the paper by
Branko Grünbaum and G. C. Shephard,
"Tilings with congruent tiles",
Bull. Amer. Math. Soc. (N.S.), Volume 3, Number 3 (1980), 951-973
and is copied from Peter Engel's paper "Über Wirkungsbereichsteilungen von kubischer Symmetrie", Zeitschrift für Kristallographie, volume 154 (1981), number 3–4, 199–215.
It is certainly remarkable that this polyhedron tiles space!
Addendum (10Oct13):
Now that Günter brought this back to the front page with
the precise citation (thanks!), I'll add
that a student Tiffany Liu and I 3D-printed copies of the
18-sided plesiohedra found by Löckenhoff and Hellner that tile space
so we could see how they fit together. Here they are inside the 3D printer: 
         

