"Is it possible for a rubber with a higher durometer to be less stiff than another rubber with a lower durometer?"
Greg's reply is generally correct, i.e. the answer is generally no.
There are a couple of oddball conditions where the above could be answered yes - one is if the rubber was poorly cured, from the o.d. in, and had a relatively soft core, with a harder (more fully cured) outer surface. Can also be done deliberately, i.e. if the core is foamed with a harder outer skin. Since a durometer test measures local stiffness only, the skin may have a higher durometer than the bulk of the material. A second condition is if you are measuring very high elongation in tensile testing relative to the (relatively small) deflections imposed by a Shore A or D penetrator. At high deflections the rubber may show a softer average stiffness than you might expect due to nonlinear elasticity of the rubber, and/or many or most rubbers will undergo strain softening (Mullins effect) with repeated loading, and you will see a decrease in apparent modulus with each load/unload cycle.