I know this is probably a stupid question but have you throughly cleaned your chamber with a proper chamber brush? It could be a possibility that the previous owner shot Wolf lacquer cased ammo through it, this sometimes can lead to the lacquer from the casings to build up in the locking lug recesses and cause the bolt to stick. This has happened with many AR-15's and since the bolt design of the G36 is based on the M-16/AR-15 then it's not a stretch to assume this could be the problem.
Next thing I can think of is to check the bolt head itself for any burs or protruding metal that has been mushroomed out for some reason or another. This could be causing the bolt to grind and stick to the inside locking lug recesses, this malfunction would not lead to any marks showing up on the casings but could still be the culprit.