The way it is now, to define a required module all one has to do is define a dependencies[] = name_of_required_module in their module's .info file. The name_of_required_module part needs to be the project's 'machine' name and not its 'pretty' name AFAIK. Please correct me if I got this wrong, but this is what I think happens while this requirement is being presented to the user in the 'Modules' administration page (../admin/modules):
a. If the module exists in the ../sites/all/modules directory (no matter if enabled or not), then its 'pretty' name is retrieved form the module's .info file and is shown in the requirement note. So one should see for example 'Requires: Administration menu' instead of 'Requires: Admin_menu'. There is also a '(enabled)'/'(disabled)' text following in order to show the state of this module.
b. If the required module is not present (the tar.gz file hasn't been downloaded and extracted to the ../sites/all/modules directory yet), then the 'pretty' name is not yet known, so its 'machine' name is shown instead. So, for example one would see 'Requires: Admin_menu' with a '(missing)' text following the note.
In case a all seems just fine to me, but in case b there are some improvement that I'd like to suggest:
1. (minor thing, I know, but still...) The required module's 'machine' name should *not* be capitalized. So, it should be 'Requires: admin_menu (missing)' instead of 'Requires: Admin_menu (missing)'
2. Since the next natural step a user takes to resolve this missing module issue is to head to this module's page and download it, why not make this a link to the project. It should be fairly simple to do! Simply convert the name to a link that points to http://drupal.org/project/+[required_module_machine_name] (prepend http://drupal.org/project/ to the module's 'machine' name).
Generally, I think it would be better if the modules' names in this page were links to their respective projects in drupal.org. Same way they are in the 'Available updates' page (../admin/reports/updates).