$n=4$ seems like the only solution.

Can this problem be solved by extremum principle, i remembered the following problem immediately when i saw this one. Finite number of chords are given in a circle, such that every chord goes through the midpoint of some other chord. Prove that all these chords are diameters.

Of course, who doesn't love a graph argument on a geo problem? Let $G$ be a directed graph where to each distinct diagonal $d_i$ we assign a vertex $v_i$; we add an edge from $v_i$ towards $v_j$ if and only if $d_i$ is a perpendicular bisector of $d_j$. We notice the outdegree of each vertex is at least 1, and the indegree of each vertex is at most 1 (since our polygon is convex). We must then have $$\sum \text{outdegrees} \geq \text{number of edges} \geq \sum \text{indegrees}$$which together with $\sum \text{outdegrees}=\sum \text{indegrees}$ implies the both the outdegree and indegree of all vertices is exactly 1. All we need from this is the lemma: each diagonal not only perpendicular-bisects another diagonal, but is also perpendicular-bisected by another diagonal. In a more rigorous manner, this follows because any desired convex $n-$gon must have a corresponding graph $G$ with this characterization. Now consider any three consecutive vertices $A, B, C$ in the $n-$gon. If a diagonal intersects $BC$, $A$ must be one of its endpoints. Moreover, by convexity, the vertex $X$ such that $AX\perp BC$ is unique, so $AX$ is also the unique such diagonal. Thus, we must have that $AX$ is both a perpendicular bisector of $BC$, and perpendicularly-bisected by $BC$. In other words, $\Box ABCX$ is a rhombus. As a corollary, $AB=BC$. Take $A, B, C$ on successive positions around the $n-$gon to show that all sides of the polygon are of equal length. Notice $n=4$ works with any rhombus; we'll prove this is the only such $n$. For convenience take $A, B, C$ such that $\alpha=\angle ABC$ is maximal. Assume wlog $B$ and $X$ are not consecutive vertices. What remains is an easy region argument, which would be nicer if I knew how to insert diagrams, but I don't If there was exactly one vertex $P$ between them, we'd need $\Box ABXP$ to be a rhombus, and it's not hard to see that $C-X-P$ is implied (absurd by convexity). Now assume there are at least two vertices between them; let $P$ be the vertex next to $A$ (other than $B$) and $Q$ be the vertex right after $P$. Clearly $P$, $Q$ and any remaining vertices lie on the region $\beta$ bounded by lines $AX$, $AB$, $CX$ and not including side $BC$. Let $H$ be the feet of the altitude from $A$ to line $CX$. By taking $\alpha$ as maximal (and assuming $n\geq 5$), $H$ lies outside of $\Box ABCX$. Now, $\Box BAPQ$ is a rhombus. So thinking of all possible lines that the diagonal $AQ$ can be (i.e. the angle it can make with line $AX$), it can be "at most" coincident with $AH$ (which would happen if $P$ lied arbitrarily close to line $AB$). More concisely, $Q$ must lie within $\bigtriangleup AHX$. It's easy to finish here, but let's be rigorous. Clearly $QX<AB$, so there must be a vertex $R$ inmediately after $Q$ (and $R\neq X$), such that $P, Q, R$ are consecutive vertices. We have $PQ=QR=AX$ and the width of $\beta$ is less than $2AX$, so the internal angle $\angle PQR$ is concave, a contradiction. Alternatively, draw line $AH$, which divides the plane into two regions each of which contains vertices of the polygon. $P, Q, R$ are consecutive, yet $P$ and $R$ lie on a different region than $Q$; observe that this can never happen in a convex polygon. Either way, we are done.

Observing the "each diagonal has to be bisected" condition makes it extremely easy and straightforward. Then consider three adjacent vertices, perpendicularity arguments - those above and in the question lead you to a rhombus where after you can prove that no point can lie outside the rhombus using convexity. That's my solution in the paper...

The only possible value of $n$ is $4$. Let $P_1P_2\cdots P_n$ be a convex $n$-gon with the this property. Choose $i$ such that the distance from $P_i$ to $P_{i-1}P_{i+1}$ is minimal. Since $P_{i-1}$, $P_i$ and $P_{i+1}$ are consecutive edges $P_{i-1}P_{i+1}$ can only be the perpendicular bisector of a diagonal passing through $P_i$ say $P_iP_j$. So $P_{i-1}P_iP_{i+1}P_j$ is a rhombus, and $P_i$ and $P_j$ have the same distance to $P_{i-1}P_{i+1}$. Unless $P_{j-1}=P_{i+1}$ and $P_{j+1}=P_{i-1}$, by convexity, the distance from $P_j$ to $P_{j-1}P_{j+1}$ is less than the distance from $P_i$ to $P_{i-1}P_{i+1}$ which is impossible by minimality. So $P_{j-1}=P_{i+1}$ and $P_{j+1}=P_{i-1}$, and the polygon is a rhombus. On the other hand, it is clear that any rhombus works so the answer is $n=4$.

MF163 wrote: Unless $P_{j-1}=P_{i+1}$ and $P_{j+1}=P_{i-1}$, by convexity, the distance from $P_j$ to $P_{j-1}P_{j+1}$ is less than the distance from $P_i$ to $P_{i-1}P_{i+1}$ @above This is not always true.

Here's a solution with the extremal principle: The answer is $n=4$, which clearly works (consider any rhombus). Next we show any $n \ge 5$ doesn't work. Let $$ \mathcal P = A_1A_2 \cdots A_n $$be the polygon. Claim 1: For each $i$, the reflection of $A_i$ in line $A_{i-1}A_{i+1}$ (say $B_i$) is a vertex of $\mathcal P$. Proof: Consider diagonal $D$ such that line $A_{i-1}A_{i+1}$ is perpendicular bisector of $D$. Then $A_{i-1}A_{i+1}$ intersects $D$ at the midpoint of $D$, which lies in the interior of $D$. Due to convexity, this forces $A_i$ to be an endpoint of $D$. Then by definition, $B_i$, the reflection of $A_i$ in $A_{i-1}A_{i+1}$ should be the other endpoint of $D$. It follows $B_i$ is a vertex of $\mathcal P$, as desired. $\square$ Lemma 2: Fix two vertices $X,Y$ of a convex polygon $\mathcal P$. Let $Z$ be a vertex of $\mathcal P$ (which varies) such that $\text{area}(\triangle XYZ)$ is minimized. Then $Z$ must be adjacent to at least one of $X,Y$. Proof: Assume contrary. Pick two vertices $A,B$ of $\mathcal P$ lying on same side of $XY$ as of $Z$ such that $A,B$ are adjacent to $X,Y$, respectively. By definition, $$ \text{area}(\triangle AXY) , \text{area}(\triangle BXY) \ge \text{area}(\triangle ZXY) \implies \text{dist}(A,XY), \text{dist}(B,XY) \ge \text{dist}(Z,XY) $$But this forces $\angle AZB \ge 180^\circ$, which condraticts the convexity of $\mathcal P$. $\square$ Now let $\lambda$ be the least possible area of a triangle formed by three distinct vertices of $\mathcal P$. Claim 3: If $\text{area}(\triangle DEF) = \lambda$ where $D,E,F$ are vertices of $\mathcal P$, then $\{D,E,F\} = \{A_{i-1},A_i,A_{i+1}\}$ for some $i$. Proof: We use Lemma 2 repeatedly. Considering $D,E$ as fixed, we obtain $F$ should be adjacent to at least one of $D,E$. WLOG $F$ is adjacent to $D$. Then by considering $D,F$ as fixed, $E$ must be adjacent to at least one of $D,F$. Our Claim follows. $\square$ By Claim 3, pick a index $k$ such that $$ \text{area}(\triangle A_{k-1}A_kA_{k+1}) = \lambda $$By Claim 1, $B_k$ (the reflection of $A_k$ in $A_{k-1}A_{k+1}$) is a vertex of $\mathcal P$. But also $$\text{area}(\triangle A_{k-1}B_kA_{k+1}) = \text{area}(\triangle A_{k-1}A_kA_{k+1}) = \lambda $$This by Claim 3 forces $$ \{A_{k-1},B_k,A_{k+1} \} = \{A_{l-1},A_l,A_{l+1}\} $$for some index $l$. Since $n \ge 5$, the fact $$A_{k-1},A_{k+1} \in \{A_{l-1},A_l,A_{l+1}\} $$forces $k = l$. This means $$ B_k \equiv A_k $$which is a clear contradiction. This completes the proof. $\blacksquare$

The answer is $n=4$. For $n=4$, any rhombus satisfies the condition. Let us prove $n$ cannot be greater than $4$. Let $A_1A_2...A_n (n\geq5)$ be a polygon. Define $B_i$ as $B_i = |A_{i-1}A_i|+|A_iA_{i+1}|$ WLOG let $B_2$ be the minimum of $B_i$s. If we take diagonal $A_1A_3$ it has to be the perpendicular bisector of $A_2A_x$ such that $|A_1A_2| = |A_1A_x|$ and $|A_3A_2| = |A_3A_x|$ If $x \neq 4$, then $B_{x-1} \leq |A_3A_4|+...+|A_{x-1}A_x| < |A_3A_x|<|A_1A_2|+|A_2A_3| = B_2$ a contradiction. Similarly if $x\neq n$, then $B_{x+1}<B_2$ a contradiction. So $n=x=4$

It is easy to prove that the greatest angle between all triples of vertices of a convex $n$-gon is one of its angles. Then consider $A_{i-1}A_iA_{i+1}$ is the greatest angle, using the assumption in the problem, the reflection of $A_i$ with respect to $A_{i-1}A_{i+1}$ is one of the vertices(say B) then two angles $A_{i-1}A_iA_{i+1}$ and $A_{i-1}BA_{i+1}$ are equal so $A_{i-1}$ and $B$ and $A_{i+1}$ are adjacent, and we are done.