SQL JOINs should scale nicely provided that the field(s) on which you are JOINing are indexed in all tables that are part of the join.

It's important to index all tables, rather than just the ones "on right right" because smart query optimizers will try to guess which of the two (or N) tables to scan first based in part on the number of rows in the table. If they happen to decide on the n>1st table, the 1st table had better be indexed on the join field(s). (It's actually quite a bit more complicated than this, but the takeaway point is that tables aren't necessarily processed left to right.)

I don't know whether MySQL does this (and now that you've asked, there goes my evening :) If it doesn't, it might in the future.

It's odd that you're finding the JOIN case to be slower from the command line. That's worth some extra examination. It shouldn't be the case.

Update: MySQL can be made to explain its query plans. See http://www.mysql.com/doc/E/X/EXPLAIN.html