I believe I have this one, but I wanted to see if my reasoning is sound since I can only find 1 such graph with this property.
Let $G$ be a graph of order $n$.
First, if $G-e$ is planar for every edge $e \in E(G)$, then $|E(G-e)|=3n-5-1=3n-6$. Thus, $G-e$ is maximal planar for every edge $e \in E(G)$. Thus, $\delta (G-e) \ge 3$ $\forall e \in E(G)$. It follows, that $\delta (G) \ge 3$. Thus, $G$ has no vertices of degree 2, and so cannot be the subdivision of any graph. However, $G$ is non-planar, and so must contain a $K_5$ or $K_{3,3}$ subdivision. So, our only option is to have $G=K_5$ or $G=K_{3,3}$. If $G= K_{3,3}$ then $|E(G)|= 9 \ne 3n-5 = 13$. So, $G\ne K_{3,3}$. If $G=K_5$, then $|E(G)|=10=3n-5$ while $K_5 -e = K_3 \vee2K_1$ for every edge $e$ of $G$. Which, by inspection, is maximal planar.
Is my logic sound? Can anyone find a counter example to this? Anything that I could be more clear about in my proof?
As Perry pointed out in the comments, there is a gap in the logic. There do exist graphs that are not $K_5$ or $K_{3,3}$ with $\delta (G) \ge 3$ such that $G$ is non-planar. However, assume that such a graph is given given as a counter example. Then since it is non-planar, it must have some subgraph that has a vertex of degree 2. Thus, some vertices or edges may be removed to yield a $K_{3,3}$ or $K_5$ subdivision, but then there is at least one edge, $e_1$ that is not a member of that subdivision, but then $G-e_1$ contains a subdivison of $K_5$ or $K_{3,3}$, and so is non-planar: a contradiction.