Military personnel locators now require that requests for information be submitted in writing and may have a nominal fee.
Locating Military People (about.com)
U.S. Army Human Resources Command (Army Personnel ONLY, AKO account or CAC login required)
U.S. Marine Corps Locator (scroll down to the Personnel Locator link)
Dudley Knox Library also has access to the FedSearch Suite published by Carroll Publishing. Within this database, you can look up a service member by their name (first or last) and title or department. NOTE: this database is best for searching high ranking / department level personnel.