Verb. To spot, stain or soil.
Adjective. Spotted or blotched; stained or impure.
Hence immaculate: unspotted, pure, undefiled.
According to the OED the first usage is in a legal roll from 1432-50, shortly followed by Caxton in 1481. Sadly maculate is now confined to medical and zoological usage.
The Panther (or Rusty-Spotted) Genet (Genetta maculata)