Hi Suzanne,
Sorry to say I made an error on my last post. She was born c 1754 not 1854!!
I would not give up so easily if I were you. Have you tried going through the military route? You may pick up something from John's records or if you think she was from a military family, you may find her father' record. Did it give her father's name on the marriage entry? If not, her father was probably serving in Ireland at the time of their marriage which should limit the timescale to search. Quite difficult without a name for her father but Maxwell is not a common name, so a matter of trawling through.
Sorry I can be of more help to you in this instance.
Elizabeth