Does not consistently providing a reward strengthen operant conditioning? When learning about Operant Conditioning, I remember being taught that not consistently rewarding the desired behavior could (seemingly counterintuitively) actually increase the strength of learning the conditioned behavior. Is this correct?

If this is correct, is it more effective to begin providing a reward at or near 100% of the time the conditioned behavior is performed, and then slowly reduce the amount to a lower percentage? Or is it more effective to simply start with a lower percentage?
What you're thinking of is called an Intermittent Reinforcement Schedule. Different Reinforcement schedules have different effects, variable ratio in particular seems to be what you're getting at:


  a reinforcement schedule in which the number of responses necessary to produce reinforcement varies from trial to trial


What's important is the behavior is reinforced intermittently but regularly enough to be "worth" it. This produces a powerful effect; I don't immediately have any sources but I do believe B.F. Skinner ran a number of such trials. where the subject will repeatedly perform the behavior in an attempt to get more rewards. 

An explanation I've heard is that with a predictable reward schedule (fixed ratio) your participant knows they can except a reward, so there's no reason to mindlessly perform the task over and over; compare a Slot Machine (variable ratio) to a machine that gives out money on a fixed number of tries (fixed ratio). A subject knows with the fixed ratio machine they can always get their reward at any time. With the slot machine you have to keep playing and playing to get that big next reward. 

Remember that for proper Shaping you should start with a high percentage (100%) initially to condition the response otherwise the participant might not be conditioned at all. Going back to the gambling example, it's much more effective if you give your participant a taste of winning when they play the slots or they'll quickly quit as it seems there's no reward to be had at all.

Shaping involves immediate rewarding behaviors approaching the desired behavior, it's certainly more important to start with a high % of rewarding, especially with non-human subjects when getting them to perform the wanted task can be problematic to begin with.