Up-smash beats inhale. King DeDeDe's inhale sucks all of Olimar's smashes into him. It also beats out his back-air from the front side of King DeDeDe. Punishing aerial dodges is fairly simple if you take the spacing required to punish the former options and notice that he is not taking either then tap the Z-button for a half charged up-smash.
Don't try to attack a DDD out of the air with Up Smash. His Back Air, Inhale, and him simply Air Dodging through it and grabbing us, all beat it out.
Ideally you want to be in front of King DeDeDe when he is about to land if you want to up-smash him safely. Otherwise the better option, as Hilt mentioned, is to pivot-grab his landing.
I believe game one and two of Fino verses Coney from MLG Columbus is viewable on http://www.youtube.com/ if you wish to see the match-up played out.