This is a Community Wiki answer, feel free to add your finds...
Field Recording Databases
Freesound >> http://freesound.org/ (added by yunque)
+ Search by license, format, bitrate, sample rate, tags, etc.
+ Open project, user-based (can search similar sounds recorded by the same person).
- Variable quality.
British Library Sounds Maps >> http://sounds.bl.uk/sound-maps/ (added by yunque)
+ Huge!
- Search by keyword or category only.
- No info about bitrate, etc.
- Mostly complex environments, not isolated noises.
findsounds >> http://www.findsounds.com/ (added by yunque)
+ Search by format, bitrate, sample rate.
- Links to other websites, license info not obvious.
SoundBible >> http://soundbible.com/ (added by yunque)
+ License info.
- Search by filename only.
Geluid van Nederland >> http://www.geluidvannederland.nl/ (added by yunque)
+ CC 3.0 entirely
- Search by tag only.
Macaulay Library >> http://macaulaylibrary.org/ (added by yunque)
+ Huge!
- $ :[
Nature Sounds . ca >> http://nature-downloads.naturesounds.ca/ (added by yunque)
+ Outdoors
- mp3 only
freeSFX >> http://www.freesfx.co.uk/ (added by joseem)
+ Easy to navigate thematic organization
+ Curated generally useful incidental sounds
+ Free commercial use, provided not main focus (full license)
- relatively small collection (a couple of thousand sounds in my estimation)