Guess what. I'm stuck on Master Rank beauty with my Manaphy. Oh such a failure I am. Ah well. At least it's... legitimate!
On topic, everything Lady Nicole and Blue_Gyarados said is highly accurate. My advice, on a more pessimistic note, is this: If you try, and try, and try, over and over again, then it might be time to raise up a different Pokemon for the contest. Preferably one that likes dry food, which is a big help.
For example, my Jynx, which clinched Master Rank with Psych Up and Ice Punch.
Therefore, I always use a move that doubles the next round's score. (Tail Glow, Calm Mind, AncientPower, etc.)
Then if I go first, I use a move that gets +2 if used first. Otherwise, I use something that always gets +3. It usually works pretty well.