The Collaborative International Dictionary of English v.0.48:

Paradoxical \Par`a*dox"ic*al\ (p[a^]r`[.a]*d[o^]ks"[i^]*kal), a.
   1. Of the nature of a paradox.
      [1913 Webster]

   2. Inclined to paradoxes, or to tenets or notions contrary to
      received opinions. --Southey.
      [1913 Webster] -- Par`a*dox"ic*al*ly, adv. --
      Par`a*dox"ic*al*ness, n.
      [1913 Webster]

WordNet (r) 3.0 (2006):

paradoxically
    adv 1: in a paradoxical manner; "paradoxically, ice ages seem to
           occur when the sun gets hotter"