My friend Matt assures me that Flood is the best in perth, so it might be worth a wait...
Try Xspeed and Cypher Industries - I hear they dabble in toyotas from time to time
I dunno if they're any good or not, but Down Under on the corner of scarb beach rd and loftus st North Perth seem to have a steady flood of high performance cars coming through (I pass by on the way to work every day) Mostly Oceanliners (R33s for the most part) but I'm pretty sure I've seen JZA80s a few times.
Apart from that, jump onto #antilag on the austnet irc network (irc.austnet.org 7000) and ask around - we're mostly perthies there.