I don't see how the contest has gotten 'cheesier' since 2004 onwards although stage shows indeed started to play a more important role at that time. The early noughties (00-02), I think, were much worse. Moreover, as Daniel pointed out, there's been a backwards trend towards simpler stage shows and slow ballads since the 'jury' re-introduction. Which also has opened the doors for another kind of cheese entries, unfortunately.
The most horrible decade to what kitsch concerns must be the 80s for me. Not only that many entries were over-the-top campy, they were also so out of touch and square or their time that it is difficult to even just laugh about them.