Though I am a native Russian speaker, however it's not very easy for me to construct such sentence as "Под одной тысячей и девятьюстами пятьюдесятью восьмью облаками" from your example. In everyday life I try to avoid such phrases. In the informal speach I sometimes use phrases where only two last numerals are not in nominative case. It's grammatically incorrect, but more easily pronounced and understandable (beware of Grammar Nazi

). It's not acceptable for writing, though. IMHO.
Numerals and their declension is one of the hardest questions even for native speakers. It's a very good test for literacy
