On the rare occasions that this has been useful I have used a slight variation on EmmEff's "wc -l" (the following comments only apply to Java but can be adapted for other languages):
cat *.java | grep '[;{]' | wc -l
that is, to find the number of occurrences of semicolons and right braces, so that you have a measure of the number of actual statements in the system rather than the number of physical lines (including blanks). This fails if your developers put all their code on the same line, but if that's the case you are already in trouble and should consider reformatting all the code.
Edit: cloc is of course a much better tool than the above command. This is just the quick-and-dirty version.
It's a bit harder to measure other forms of "code": we also create lots of JSPs, object models (using a web-based tool so there is no text file involved) and of course populating databases with metadata can be an equivalent. Harder to use grep to measure all those, though you can come up with a proxy such as number of attributes in your data model, or number of records in the metadata tables.
The most sensible way to think of "lines of code" is to see them as the atomic unit of a programmer's thought. This is why high-level languages are much more productive both in time, and in lines of code - a single thought represents a much higher level of abstraction and therefore has more power. Simplifying drastically, a given programmer has the capacity for a given number of thoughts-per-hour, and so lines of code as a proxy for that is a (grudgingly) semi-legitimate measure.
I appreciate why a code review company would use it as a measure of their likely workload, though it is a bit unimaginative. Maybe you can persuade them to think instead in terms of the business value they are going to add through their services.