How MUST the directory for a plugin be structured?

How does WordPress determine “the main plugin file” ?

It is the file in your plugin that contains the plugin header comment

/**
 * Plugin Name: A fresh example
 * Plugin URI:  http://example.com
 * Description: Foo makes a bar
 * Version:     2012-06-14.1426
 * Author:      John Doe
 * Author URI:  http://example.com
 * TextDomain:  your_textdomain
 * License:     MIT
 * LicenseURI:  http://www.opensource.org/licenses/mit-license.php
 */

Q1: Is it legal / supported to have a plugin that is structured like this:

Yes. Every directory structure (as far as supported by servers) is legal.

Q2: If so, how does wordpress determine which php file is the main plugin file?

See above ↑

Q3: Is the use of a subdirectory (like inc/ in the above example) a requirement when the PHP code spans multiple modules?

Requirement? No. Nicer to read: yes. Easier to maintain: Also yes.

Q4: Is it true that there should be a maximum of ONE php file in the main plugin directory?

No. Simply no.

Summed up

The way you’re organizing your files and directories completely is up to you, your personal preferences and nothing else. If you want to make it easier for you to maintain and for other developers to step through your code, then you should use some sort of file/directory organization.

Examples

I personally append .class.php as extension, when I got a class in it. I also name my files right exactly like the class. The reason is simple: My “main plugin file” – which is my bootstrap class, normally cares about loading all the needed stuff.

// inside my PREFIX_bootstrap class:
public static $includes = array(
    'settings'          => false // Parent class - no need to hook
   ,'settings_extended' => true  // Extending class - hooks static init() on `init` hook
);

public function construct()
{
    // The prefix for every class in my plugin
    $prefix = 'my_class_prefix_';

    foreach ( $this->files as $handle => $hook )
    {
        require_once plugin_dir_path( __FILE__ )."{$handle}.class.php";

        if ( ! $hook )
            continue;

        $class = $prefix.$handle;
        class_exists( $class ) AND add_action( 'init', array( $class, 'init' ), 1 );
    }
}

This means my classes and files are named like the following:

• settings.class.php AND settings_extended.class.php
• my_class_prefix_settings AND my_class_prefix_settings_extended

I also do some basic directory organization, like storing all js/css/img files in directories named like this.

Some people use (for larger plugin) folders that are named inc/includes/assets/extensions/lib/etc.. I’d recommend to use subfolders for large plugins only. If you got additional stuff like widgets, etc., then you could use specific subfolders for them.

Last word: No, nothing what you’ve found is true, those (like the stuff I showed you) are only recommendations.