I guess it depends in what kind of environment you operate. In europe for example the use of RNAV is required above a certain level (FL95 for most countries) and an out of date nav database is not approved for operation in that airspace.
Our 737 MEL has therefore an entry that allows all nav databases to be out of date only if there is no requirement for any RNAV procedure or navigation and of course as long as you have current charts on boards (charts are no longer required in dual FMC installation with EFB installed which may be inoperative as well). If you want to use any kind of RNAV procedures, no matter if enroute, approaches or departures, you need at least one current nav database on board and usable for the crewmember responsible for navigation.
You can allways try to file a non-RNAV flightplan, i had to use that once when our FMC forgot its database completely every time the aircraft was powered down. However that was a purely domestic flight and prior approval by any ATC unit in contact during our flight was necessary. On another occasion where we still had the FMC but the FMC-AP interface was gone we couldn't fly into switzerland as neighbouring country because they would not approve us without PRNAV, the aircraft was AOG until the problem was fixed.
To be honest i have never seen an out of date nav database in airline operation on the 737 so far, with good maintenance procedure and the possibility to pre-store the next database up to 27 days prior the date it becomes active it seems easy to keep them current.