Just for the record, if I let my engine play 5 half moves with search
depth 5
(total 324 knodes searched), these are the results:

king-pawn table size %hits %table full
1 30%(!) 100%
10 42% 100%
100 60% 100%
1000 74% 100%
10000 85% 91%
100000 89% 21%
1000000 89% 2%

So it looks like in 30% of the node lookups, the pawn structure didn't
change
(table size = 1 has a 30% hit rate!), even in the opening moves.

I'll go for a size of at least 100000, since it doesn't cost much
memory. Actually I store 4
scores in the table: king safety (black and white) and pawn structure
(black and white),
the king safety term is further processed in the evaluation function
(scaled with opponents'
material, king safety can only be bad if the opponent has sufficient
material).