I can't answer this from a programming perspective, I can only give you my observations as someone who contracted in support roles for approx' ten years and has recently gone perm. The was partly due to the reasons you hint at above, namely lots of young, cheap people with no experience but lots of exams who suddenly become experts ! :-)

I find it strange that any reputable agency would give out your CV to another company, they normally like to play things close to their chest and should contact you before forwarding your CV to anyone but this appears to be indicative of the whole agency industry these days. Was this a bona fide IT agency or someone like Adecco, or Alfred Marks, your common or garden temping agency? When I started contracting you would lodge your CV with an agency and then update them as you progressed through contracts and they would phone you if they had a likely contract. Nowadays, you have to apply for each job even if it is with an agency who already have your CV. It seems to be that all they are interested in is harvesting CVs and I suspect there is a trade in selling them as well. If you are concerned about agencies, there are contractor websites(sorry don't know any off the top of my head) that would be worth reading and may tip you off about bad agencies. You don't need to be thinking about contracting to check them out.

with regard to certification, I have worked with people who have no certification and been excellent. I have also worked with people who are certificated upto their eyeballs and been less than useless. We had one contractor (MCSE) who wouldn't do any support(desktop, server) "I'm here as an architect" he whined, he was kicked out the next day ! It would certainly do no harm to study for some certification and would remove the opportunity for them to discard you at an early phase, but there are other options to these so-called professional training companies. Local colleges, night school and good old doing it yourself with the manuals and test questions. In your situation I would go the self paced training route.

So far as getting work goes; have you tried jobserve and searching for contract/permanent roles in your local area ? There always seem to be plenty of junior roles advertised - even think about desktop support roles etc and work on your programming in your own time(as a non programmer I can't really say for certain, but if you did contribute to Open Source projects etc. and have something to put on your CV, it should help) - it's all experience. All you'd be looking for is a foot in the door position. I've no idea what part of the country you are in, but you could try The Evening Standard in London on wednesdays(I think) for IT jobs, or other local rags.

Sorry if I sound like a TOG (when I was young we used to live in shoebox in middle of road etc. etc.), anyway I'll be interested to hear other peoples take on things.