This question can't be answered if you don't tell us what system you use. The CORE system is as follows:
M - F Str +0
F - T Str +2
T - S Str +4
S - M Str +4
M - L Str +8
L - H Str +8
H - G Str +8
G - C Str +8
You already said you use Str +16 for each size increase after that, but do you use the core system for the previous sizes, as shown above? If not, give us your table. Personally, the core way of doing strength works PERFECTLY though and has NO flaws, so there is no reason to modify it.
Further numbers can be extrapolated easily. Str +16 for the next 8 sizes, Str +32 for the next 16 after that, etc. It works, so I think UK is WAY off on that one.
Anyway, damage. According to the core rules, per size increase:
1d2 - 1d3
1d3 - 1d4
1d4 - 1d6
1d6 - 1d8
1d8 or 1d10 - 2d6
1d12 or 2d6 - 2d8
2d8 - 4d6
4d6 - 4d8
4d8 - 8d6
8d6 - 8d8
8d8 - 16d6
16d6 - 16d8
16d8 - 32d6
32d6 - 32d8
32d8 - 64d6
64d6 - 64d8
64d8 - 128d6
128d6 - 128d8
128d8 - 256d6
256d6 - 256d8
256d8 - 512d6
512d6 - 512d8
512d8 - 1024d6
1024d6 - 1024d8
1024d8 - 2048d6
2048d6 - 2048d8
2048d8 - 4096d6
4096d6 - 4096d8
Do you use the core system as it is (shown above), or did you change it? Using the core rules modified for further size increases, with UK's strenth modifiers or the extrapolated core rules, there is only one thing that I found that fills the criteria.
A HALF-DRAGON HEAVY WAR HORSE with 26 size increases (making it Colossal+23) has Str 418 and does 4096d8+102 damage with one of its SECONDARY ATTACKS (which give only half the strength bonus in damage), and since the thing is already Large, it has wings and can fly at its normal speed!