Boolean functions with exponential size OBDD representation in all orders except one order?
If there is an variable ordering $\pi$ such that the OBDD size for $f$ with this ordering is $O(poly(n))$, then a lot of OBDDs with a similar variable ordering has a size of $O(poly(n))$.

To see this you can swap neighboring variables in $\pi$, i.e. for $\pi = (x_{\pi(1)}, \ldots, x_{\pi(n)})$ you construct $\pi&#39; = (x_{\pi(1)}, \ldots, x_{\pi(i)}, x_{\pi(i-1)}, x_{\pi(i+1)}, \ldots, x_{pi(n)})$ for some $i$. The OBDD size for $f$ with variable ordering $\pi&#39;$ is also polynomial because you can store the value of $x_{\pi(i)}$ by doubling the $x_{\pi(i)}$ nodes in the $\pi$-OBDD for $f$. Then you have the information of $x_{\pi(i)}$ and $x_{\pi(i-1)}$ at this nodes and you can use the $\pi$-OBDD to go on.

That means if you swap $O(\log n)$ variables you also have a polynomial size OBDD.