Working through CLRS completely is a very time consuming task I think Bradford intended that book as a reference, but yes, you need to work through some of the stuff in order. For example, you need to be fairly conversant in Linear Algebra, probability, and proof technique before you can tackle Bishop, else you won't make much progress. Once you get some basics under you (especially the underlying math stuff) you'll end up being able to read through an ML book the way you can read through a moderately tough book in programming.
" I managed to eventually read through MacKay (enjoyable book and available as a free PDF, too) and feel I have already forgotten most of it again :-("
The best way to learn this stuff is to have an eventual project in mind. I ended up learning most of this stuff because I was working on a Robotics project for the fine folks in the Indian Defence Depts and was very much "thrown in at the deep end" - nothing like it to accelerate learning but I wouldn't wish to do it again. for the first few weeks I couldn't (literally) understand a single sentence in an hour long meeting. Very humbling.
Depending on what exactly you wish to do, you maybe able to avoid many of the books. If you think I can help you narrow down to a smaller list , please ask here or send me email (my email id is in my profile).
But yes, in the end Norvig's point applies here too (as Bradford points out. I have been working in ML for 8 years now so still 2 years to go :-P) .
OTOH I am just a programmer who got bored with enterprise software and have no formal training in math (or CS for that matter) and if I can do it anyone (certainly anyone on HN) can.