Surely any characteristic that has been created or optimized by natural selection must be highly heritable.

That's not true. On the contrary, heritability is defined as the part of the observed variation in a trait that is due to genetic differences, and if there has been intense natural selection on some trait, it may be that only those organisms with the same favorable genes for that trait have survived it, so that now there is almost no genetic variation at all.

Note that saying that a trait is heritable and that it's determined genetically in some general sense are two very different things. A trait can be under almost exclusive control of genes, with next to zero environmental influences, but if all the organisms of the species have the same relevant genes, its heritability will be zero. For example, humans are clearly genetically predisposed to develop two arms, but the variation in the number of arms is almost wholly environmental -- people lose arms in accidents, wars, etc. much more often than they get born armless due to genetic causes. So if you calculated the heritability of this trait (the number of arms), it would be near zero, and yet it's clearly absurd to say that the number of your arms is not genetically determined.