The eslcafe thread has confirmed pretty much the order of things.
Come to Japan on a dependant visa. Look for work. Get permission form from immigration, go back to prospective employer, have him fill it out, give it back to immigration, get to working.
Of course, it's in more detail over there if anyone wants a look at it. I'll just try and confirm how much work is part-time work in case this can help any other dependants in the future.