I came up with an idea - if every block stored which team it was placed by, it could be made more difficult to dig blocks placed by team-mates. Either the time taken to dig team-mate's blocks could be increased, or a limit on the number of team-mate's blocks you are able to dig per life could be implemented. The time increase could also be incremental (the more team-mate's blocks you destroy the slower it becomes).
The team value could be stored in a single byte or even a boolean if null can be used for map blocks. The fact it would also effect your own blocks would probably be a good thing if anything. This would hopefully discourage certain players from laboriously sabotaging their own team...