Does anyone know any commercially available flexible high permittivity (>20) solid material?
You’re very unlikely to find those commercially. Most substrate, even hard substrate have an epsilon under 12. There are a number of webpages with dielectric constants of random materials out there, here is one. The only materials with dielectric constants around your values are exotic and possibly dangerous ceramics (uranium oxide = 26, but that doesn’t look like something one would want to use as a substrate), and organic compound with high liquid content. My best guess would be to look for hydrogels or alcoolic gels. Depending on your requirements, they may be other simpler solutions, like metamaterials.