Yes, big dilemma, get creative, here's what I've done:
To get anywhere these days with a new site (no PR muscle) you have to pay your way in! So, I found a web-developer who fortunately had about a dozen different sites all relevant to my business (travel) and paid a modest fee for about 50 randomised inbound links - 10 deeplinks from each site (one way - don't link back to them or google sees a relationship). Each of these pages were PR5 some even 6. In due course this gives me a respectible PR4 on lots of my pages. Then I get hold of lots of relevant sites of PR3 and lower and start building links with them - these are usually people who know little about SEO and are simply obliging a link exchange. Enough of these will soon give you a PR5 and maybe more on your homepage. Then you have some muscle to go after the big boys. By now of course you would've ceased to pay for the links you initially had to 'buy'.
Of course google is now ranking more according to lots of relevant links as opposed to straight PR strength, so all the little guys count.
It may seem like a waste of time emailing back and forth to get some PR3 site to link to you but they are also more willing to place your link on a page full of terms relevant to or similar to the keyword of the targeted deeplink on your site. These are gold nuggets, far better than a link on a PR5 page in a links directory that has numerous other outbound links and little targetted relevance to the deep link.