I just discovered Recruit.net through the Web 2.0 indeces somewhere. These guys are doing it right in my opinion. They are leveraging 3rd party data (job postings), allowing customization (profiles with resumes), really clean interface, well placed ads and a site that works.
I think they can work on their search function – I tried playing around with different terms and with a mix of operators and wasn’t highly impressed with my results and result sort options. They currently only feature Australia, China, Hong Kong, India, Japan and Singapore; maybe more countries would be good.