To your specific question of (easily satisfied) plausibility, the answer is yes. Since you seem to be looking for a broader critique. You seem to be mostly on the right track, but a few things are making your description overly complex.
It looks like your Classes table is more like what I would consider a course to be and your departments_teachers_and_classes is more of what I would expect a Classes table to be. A course would be Math, but a class would be the Math course taught by a particular teacher during a particular school term. A class is like an instance of a course.
To carry this change through, your departments_teachers_classes_and_students could simply be ClassStudents.
It seems as though you are using the department concept on several different levels. You should decide where the department belongs and stop referencing it everywhere else. You've said that a teacher can teach for multiple departments, so we can't put the department in the teachers table. This leaves Classes and Courses. Whichever you decide, it need only have a foreign key to the Departments table (unless you decide that one can be in multiple Departments). This eliminates the Departments_and_teachers table.
Teachers_and_Students could be replaced with a teacher foreign key in the Classes table and students/classes foreign keys in a ClassStudents table.
In short, for the portion of the design you have described, you probably need the following tables:
Departments
Teachers
Students
Courses
Classes
ClassStudents
Terms
You need to learn the difference between repetition and redundancy. Sometimes a field value is repeated coincidentally. This kind of repetition cannot be normalized out.
Normalization is about studying the functional dependencies between key and non-key elements. It is not about putting everything that might occur twice into a table with a surrogate key.
For example, you say that a phone number may be used by multiple companies and have modeled phone number as an independent table. This would prevent update anomalies if when one company changed its number all of the other companies using that number changed theirs at the same time and in the same way. Does any of that actually make business sense? It doesn't to me.
Also, normalizing geography into a hierarchy is a questionable proposition. However, you haven't even normalized into a hierarchy. Is region ID not determined by country ID? If so, your LOCATION table is not 3NF. Similarly, are there postcodes that bridge states? I don't know the Australian system well enough, but I know that in Canada, the US and the UK this doesn't happen.
You've designed everything like its a star schema and company is the fact. Facts in star schemas are usually transactions, not static entities. Transactions don't tend to change their properties, because they usually represent something that actually happened and one doesn't generally go back in time to change history. Static entities live for a long time in your data (maybe forever) and change their properties fairly often. Star schema is not a good, efficient model for this type of data.
What you should do is run queries on the frequency distributions of each column and on combinations of columns that you think may be keys combined with columns that you know aren't keys. This will help you test your assumptions about which columns are truly able to act as keys. Then you should temper those findings with some common sense around what could potentially happen to your data in terms of changes to column values. Once you know your actual functional dependencies found in your data, then follow the relatively mechanical process of moving your relation to 3NF.
Best Answer
I think you need to reconsider whether the payment for the dates is done on the hire (or rather the transaction) or the customer.
When thinking about normalization you need to think in terms of properties of an entity rather than something abstract so I want you to think if day in and out, and the paid column are really a property of the customer rather than the transaction (I guess the price of the transaction is a giveaway).
I think, if you think about it that way (entities-properties) you will feel naturally that the price and the dates and the paid go together with the renting transaction rather than the customer. (possibly needing a date for the transaction in the case of returning customers, but that isn't included in your original table)
You might also want to reconsider storing the item name on the transaction instead of just the item number. Items could be a table in itself.
It's usually not abstract theory but what you feel as properties of an object that is right. It's not that much different from class/object design in programming.