Thanks for some great replies.
To be a little more specific about our situation. We are a small military operator. The FMS is new to our aircraft and the MEL does not (yet) include the FMS database.
While the MEL has some specific rules for civil operators, they differ to ours. Our MEL is part of our SOP and is to be used for guidance (and I don't mean that dismissively). The fact that it is not in there, means it is at the aircraft commander's discretion, as in fact it does for all the items that are in there.
From an operator's perspective, we are good to go. I really wanted to know what legislation there is out there from outside of the operator's perspective (we will take it if we're allowed to).
I have no doubt that we can navigate the aircraft accurately as all the information going into the kit to control our navigation will be current (as cross-checked from current documents including up to date charts). I believe that we are meeting our obligations to ensure accurate and safe navigation (unless there is legislation which says otherwise). We do not have datalink.
Once again, thanks for your perspectives.