I'm using optus $50 blackberry unlimited plan. I'm not sure whether you can sign up to this without linking it to a BB, as i just used the same settings in the iPhone to my BB and gprs works fine.
slow, but fine.
BTW: telstra is the only company that offers EDGE in Australia, the rest offer the slower gprs.
Also, if you cant get on the Optus BB unlimited plan, which is a shame as it's pretty much the only unlimited plan i could find, try the Virgin 300mb cap which is only $10 per month.