I don't expect any "homeruns"; but I don't need to be told that this
is hard.

Given a woman' s maiden name provide a methodology that will supply
that woman's married names approximately 95% of the time. I am talking
about American woman of age presently greater than 18, born after
1920.  I am aware of the implications that most younger woman will
have their maiden names.

I am offering only $10.00 because I am cheap and I don't expect this a
problem of methodological interest that I don't expect it to be solved
in a satisfactory (to me) way.   Like art, I will only know a
satisfactory solution when I see it.  Surprise me!  Surprise yourself!

There is a way in the UK and you probably have similar resources
wherever you are.

We have a place called the Family Record Centre in London where
visitors can plough through every marriage in England since long
before the time you have specified.

This comes free but te snag is that it's all manual work.

As far as I know, there's no computer-based service available to the
general public.

Probonopublico mentioned the Family Record Centre in London. The
indexes of these records are being transcribed and are available
on-line:

http://freebmd.rootsweb.com/

If you know her date of birth then there are paid services like
AnyBirthday.com that can help. There is also a small chance that she
has registered at a site like reunion.com where old high-school
buddies trace each other. Otherwise, forget about it.