I'm with you on this one, shanks, and so is the Usage Panel for the fourth edition of the American Heritage dictionary (2000):


Complement and compliment, though quite distinct in meaning, are sometimes confused because they are pronounced the same. As a noun, complement means “something that completes or brings to perfection” (The antique silver was a complement to the beautifully set table); used as a verb it means “to serve as a complement to.” The noun compliment means “an expression or act of courtesy or praise” (They gave us a compliment on our beautifully set table), while the verb means “to pay a compliment to.”