Welcome to RootsChat - we will do our very best to help you.
Trying to answer the last part of your query - heavens, it is difficult to say just what percentage of parish records are available online or on CD. The flippant answer is - not enough!!
We are always looking for extra information.
The important thing to remember about indexes like the IGI (FamilySearch site) and CDs is that they are all secondary
sources. Ideally you should check the originals if at all possible at the record office or using the microfilms availabe through LDS Family History Centres. Lots of family history societies have produced indexes and transcripts of various material (baptisms, marriages, burials and memorial inscriptions) either in book form, on microfiche or more recently on CD. You may also find online transcriptions of some registers - try a google search - it's amazing what you might come up with. Also have a look at this site if you haven't done so before:http://www.genuki.org.uk
Have a good wander around all its pages - lots of links and information to help get you started.
Back to the marriage of Thomas Randall and Rebecca - I have looked at the BVRI2 (another index which complements the IGI and has fairly good coverage of Wiltshire) but their marriage is not included. This does not mean that they married outside Wiltshire - only that wherever it was is not included in the index.
As far as the 1871 census is concerned, someone will look that up for you, but can you give a bit more information, like names or ages of the people you are looking for. It would help whoever is searching.
If you have any more questions, just post them on here and some kind soul will try to help you out.