steve, when I was running my own business I got letters like yours on an almost daily basis. It's tough to point you in the right direction. What you are doing is a good start, get the word out. Many on here are more impressed by turning up IN PERSON to a place of work, beit a building site, company office, whatever, shows effort. Where is the effort in mass mailing thru the yellow pages?

When I was serving my time there was an older apprentice there, although he was employed thru his da.
Many think it's better having an older apprentice too as they are less likely to be unreliable having passed the "lets get pissed" stage!

All I can say is keep approaching employers, offer to work for free etc. Make a good case as to why you would benefit their company(remember in business money talks). Think of why plumbing is the trade for you and make a case for taking you on.  Get in touch with SNIPEF and see what they have to offer. They will have a good idea of whats available in your area(and they are based in edinburgh) [Note apprentice wages on that site! can you survive on that??]

Good Luck.

btk