OCaml + Batteries, 138138 117 characters

let n x=fold(fun y i->y-(x lsl i land 1 lsl(i+i)))170(0--3)
let m s=Char.(String.(of_enum[?chr(170-Enum.sum[?d d|c<land
p*p|p<-List:[1;2;4;8]?])|c<-enum s/@code;d<-List:[n c;n(c[c;c/16)]16]?]))

Tests:

With

let hex s = String.(enum s/@(Char.code|-Printf.sprintf "%02x")|>List.of_enum|>join" ")

The results are:

m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x10\x02" |> hex;;
- : string = "aa a9 a6 aa"
m "\xFF\x00\xAA\x55" |> hex;;
- : string = "55 55 aa aa 66 66 99 99"
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x01\x02\x03\xF1\xF2\xF3" |> hex;;  
- : string = "a9 aa a6 aa a5 aa a9 55 a6 55 a5 55"

As a benchmark, with:

let benchmark n =
  let t = Unix.gettimeofday() in
  assert(2*n == String.(length (m (create n))));
  Unix.gettimeofday() -. t

I get:

# benchmark 16_384;;
- : float = 0.125038862228393555115520954132080078

on my MacBook.