FYI, the phrase originates from the difficulty and danger of carrying out certain adjustments on a sailing ship: http://en.wikipedia.org/wiki/Between_the_Devil_and_the_Deep_... - it's not about having the Devil to pay, but what you risk if you don't get the job of adjusting your 'sails' done.
Those certain adjustments are "paying the devil." The "devil" being the gap between the main deck and the hull; "paying" being filling with pitch. When you are doing that, you are hanging over the side, "between the devil and the deep blue sea." When you are between the devil and the deep blue sea, paying the devil, the sails are down. Adjusting sails has nothing to do with it.