What problem cannot be solved by a short program?
For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose.

There are some interesting results, however. Encoding of randomly generated strings will always require a cost proportional to the size of the string. Pigeonhole principle tells us there will always be some functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases. And Blum's size theorem tells us that, for a total language, there are always functions you can encode larger than an arbitrarily chosen blowup factor compared encoding the same function in a Turing complete language.