How does dropping ordnance affect the weight and balance of the aircraft? During a mission, military aircraft often shed a lot of weight from takeoff to landing.  

An F-15C (empty weight: 28,000 lbs) carries an internal fuel load of 13,455 lbs (almost a third of take-off weight not including pilot and ordnance).

A cargo plane like the C-17 may perform a combat off-load while airborne.

Meanwhile, the aircraft I worked on in the army were deadlined whenever 1% of total aircraft weight was removed, requiring either the part to be reinstalled or a total reweigh prior to next flight.

Operationally speaking, how are these "fat burning exercises" completed without jeopardizing crew and equipment due to shifting weight and/or CG?
the aircraft I worked on in the army were deadlined whenever 1% of total aircraft weight was removed, requiring either the part to be reinstalled or a total reweigh prior to next flight.


That's for internal equipment, which will affect the empty CG data.

All aircraft lose weight during a trip. Aircraft designed to lose a lot of weight all of a sudden ( C-5 airdrops, B-52 carpet bombing ) have the details and limits calculated during the design. In the case of bombers, the ordinance will be hanging near the wings and will have a specific release order, usually back to front. 

A tailgate aircraft dropping something will also have very specific procedures based on the weight of the pallet going out the back door. If it's delivering pizzas the procedure is along the lines of "whenever, dude". If it's a tank, it has to be positioned and locked down until the moment of release.

The above is very noticeable by the flight crew.

If the load stays (or gets stuck) on the back ramp, you're usually done. I used to skydive - 10 people on the back end of a smaller tailgate like a Casa can and do cause the plane to stall. The rules were stay at the front until it's your turn, then position and exit in a prompt manner. If the buzzer goes, let go NOW. Unlike a cargo plane, jump planes have 12,000 feet to recover from the stall.