"There may not be one perplexity value that will capture distances across all clusters—and sadly perplexity is a global parameter. Fixing this problem might be an interesting area for future research."
There are some suggestions in the literature for fixing this. Michel Verleysen's group suggested a "multi-scale" approach:
https://www.elen.ucl.ac.be/Proceedings/esann/esannpdf/es2014...
http://dx.doi.org/10.1016/j.neucom.2014.12.095 (more details in this one, but behind a paywall)
Their approach is to calculate the input probabilities using multiple perplexities and use the average. They also suggest tweaking the output probabilities, but it uses a free parameter that isn't present in the standard formulation of t-SNE (their suggested algorithm takes the same approach as t-SNE, but uses a different cost function and output weighting function).