This tactic was once used very succesfully by an old friend of mine who used to have his mailbox victimized semi-regularly.
The first step is to buy two mailboxes, one being the biggest that you can find, the other being nearly the smallest.
Buy a bag of cement at the same time.
Mix some cement, and fill the large mailbox about halfway. While it is still wet (read: immediately) place the small mailbox directly centered inside of the cement filled large mailbox.
Fill the larger mailbox with more cement, leaving just enough room to make sure that the smaller concealed mailbox still has enough room to open and close.
When the double mailbox/cement contraption has set, put up a sturdy mailbox post and place the entire thing out in front of your house.
The Mailman will still be able to deliver mail to you (by opening first the large, then the small mailbox doors). However, the first time some little punk tries to smash it with a baseball bat he'll be lucky if he doesn't break his arm.