Problem is that teamcity is not 100% clear about how the regex works.
It only operates on a per-line basis. I needed to check the complete log file. This was ultimately solved by having msbuild output the log file to a separate location and check it using a new build step.