Whilst I prefer to feature places worthy of note, this page, detailing all the accommodation used on a tour, has been added in response to requests from those planning similar routes. Click on the green address boxes to reveal more details and please let me know if anything is out of date.

John O'Groats Youth Hostel - Canisbay, Near Wick, Scotland. KW1 4YH
Contact: John O'Groats Youth Hostel
Phone: +44 1955 611 761
Email: N/A
Web Site: Open in new window.
Small, and just about as basic as hostels get, but we weren't complaining, the bikes were safely locked away and it's a dead handy place to start the tour from! No food (as per all Scottish youth hostels) so, if you don’t have your own food, a ride into John O'Groats will be on the cards.
2012 Feedback: It seems that the hostel is no longer in operation, which is a shame as local alternatives are limited.

Tordarroch - Castle Street, Dornoch, Scotland. IV25 3SN
Tordarroch is a nice place and Rose is very helpful (even offering to dry our laundry for us.) The packed lunch we had prearranged and breakfast were both of a good quality.
Our bikes were safely stored in the back garden, the tarpaulin offered to cover them was not required.

Carn a Chuilinn - Golf Course Road, Fort Augustus, Scotland. PH32 4BY
Nice location at the south end of Loch Ness

Oban Youth Hostel - Esplanade, Oban, Scotland. PA34 5AF
Large, friendly and popular hostel that could have claimed four stars if they had served food, but the Scottish YHA don't, so they loose out because we had to search for our breakfast. :-(
Great in all other respects, though the town of Oban itself is probably responsible for a lot of the good will.

Strathwhillan House - Brodick, Isle of Arran, Scotland. KA27 8BQ
Very handy for the ferry to the mainland if heading south, but those heading north may want to push on to Lochranza's youth hostel for the ferry in the other direction.

Low Kirkbride Farm - Auldgirth, Dumfries & Galloway, Scotland. DG2 0SP
A little remote but worth it! The only place to greet us with pots of tea and homemade cakes. Evening meal available by prior arrangement as well as a hearty breakfast and packed lunch.
Bikes can be left in a cattle shed and will be safe because you are miles from anywhere!

Keswick Youth Hostel - Station Road, Keswick, England. CA12 5LH
Offers dinner, breakfast and even a packed lunch service; cant comment on how good the packed lunches may be, because we forgot to collect them before we left!

Willow Cottage - Thropps Lane, Longton, Preston, England. PR4 5SW

Ty-coch Bungalow - Llanymynech, Wales. SY22 6QZ
Contact:
Phone:
Email: N/A
Web Site: N/A
Details are deliberately sketchy, hopefully there are enough to help you avoid it!

Burton House - 19 St. James Square, Monmouth, Wales. NP25 3DN
Contact: Burton House
Phone: +44 1600 714958
Email: N/A
Web Site: N/A
Not sure if this guest house is still in business, their web address site is no longer on-line and their domain (burtonhousemonmouth.co.uk) is available for purchase, which doesn't bode well.
If so, it will be a shame, because it was a friendly place and an enjoyable stop; though the rooms would have benefitted from a little maintenance

Street Youth Hostel - The Chalet, Ivythorn Hill, Street, England. BA16 0TZ
Pleasant and quirky little hostel. Self catering only though and Street isn't overly endowed with dining facilities; we did eventually find a very nice Italian restaurant in the high street though.

The Old Bakehouse - South Molton Street, Chulmleigh, England. EX18 7BW
This was a lovely place to stay with an excellent restaurant and cyclists are very welcome.
Be aware though, you will probably be facing a 20% climb/push into town when travelling north to south - sorry!

Golant Youth Hostel - Penquite House, Golant, Fowey, England. PL23 1LA
A good, family friendly, hostel. However, its pretty remote and not actually on the tour's route, so of limited use to those following a similar path unless you have backup.
We had been joined by my family by this point in the tour which gave us the luxury of being able to select the accommodation from a larger catchment area.
A word or two about the ratings...
First off, the only 'fail' is a one star rating. Two stars is the 'per expected' default, indicating all was okay and your stay should be pleasant enough.
Three, four and five stars increasingly highlight that things were better than expected in terms of price, location, hospitality, friendliness, facilities or bike security; the more stars, the better these factors were.
Finally, the ratings are all relative: its easier for a camp site or hostel to score higher than a guest house or hotel because they're cheaper and expectations are lower.