As a native speaker I would say 'Cuțitul este pe masă cu brânza.' because I'd be talking about a specific knife and a specific piece of cheese ('Cuțitul și brânza se află pe masă.')
'Pe masa mea' ('On my table') or 'pe masa aceea' ('on that table') would use the definitive article as well because I'm talking about a specific table.
'Pe masă' has been described in many other responses as being more general, as a state of being or placement if you wish, not on a specific table. Same idea with 'la bucătărie' ('in the kitchen').
Oh, and since 'cu' is a preposition as well, I'm not convinced that 'pe masă' is indefinite due to the use of 'pe.'
Perhaps this will provide a much better explanation:
If you scroll down to the next page, there's even a discussion of the three aspects of the definite article that can cause problems, with "pe masă" being used as an example.