you know how when you get kills with a certain gun you rank up right? go from novice to adept to expert to master or whatever it is, how about this: at each gun mastery milestone, the player should unlock unique abilities specifically for that gun! This would reflect his increasing skill with that weapon and make him more competent in its use.
For example lets say that I just recently became an expert with the assault rifle. the expert ability I unlock is a minor decrease in bullet spread when using the assault rifle. Now I keep using the assault rifle and get to master, and unlock boosted red reticule range for the assault rifle! that would be pretty cool huh?
each gun could have a totally unique set of rewards for each of them, designed to enhance that particular gun to the fullest upon mastery. This would also give incentive to have players master all the guns, and of course add lots of new strategy and entertainment to halo! whatcha think?