I don't know K-Lite specifically but I'd say the codecs are going to depend on the patents involved. They won't legally be able to release the patented information related to .mp3 though they may be able to provide the binary code that dicifers .mp3.

Is your mandate to use only open source, only freely open source or only legal software which works on open source platforms be itself open or cosed source?

I'd say if you go with Mandriva, Suse or Canonical where a deal with the patent holders has been made; there shouldn't be a legal issue by including them. The fee for Mandriva Powerpack includes the license for the patent questionable software; same as Windows fees including license costs for patents not held by Microsoft (.mp3 and DVD there also).

What is it that your company does which requiers consumer multimedia codecs?