I have a Radeon R7 370 and running Mesa 12.0.1, I get horrible performance in
certain areas or events of POSTAL 2, to the point where the game is almost
unplayable. 

This issue is easiest to reproduce on the level with the bank. Approaching the
bank causes the framerate to get lower and lower, and entering it causes the
game to immediately freeze for several seconds. If you rob the bank, the
resulting firefight will cause the game to freeze repeatedly.

Using the exact same hardware, I've played the game using fglrx with much
better performance. Help would be much appreciated.