How serious should I regard the "compliments" in an email denying my application? A school, whose PhD program I applied to, denied my application with words such as "Your record is strong, but...". I am kind of confused. Is such a reply simply a "polite" way to decline a person? Should I believe that the sentence "your record is strong" is a compliment, or it is simply a decoration?

To me, such a compliment does not seem to help because obviously, for the school, my record was not strong enough to be admitted, so speaking of "your record is strong" is almost meaningless?
I would take it as simply a polite way to decline your application.  They no doubt really do get a lot of strong applications (every decent program does), and in many cultures such as the US there is a tendency to "sugar-coat" bad news with compliments (I don't know if your application was in the US, but I believe this practice turns up elsewhere as well).  You would actually probably get less praise if you got in---after all, the acceptance is compliment enough.