What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)
This is not an answer, just a comment.
Frank Lutz in Berlin is one of the experts on this topic, and you might ask him.
He maintains a nice web page,
The Manifold Page, which includes lots of information and references, including
descriptions of 
Barnette's non-polytopal 3-sphere and
Grünbaum-Sreedharan's non-polytopal 3-sphere.

Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):


  Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?


For sufficiently large genus (I think 5?), there are non-realizable examples.