How do we know that nuclear decay is truly random and spontaneous? Nuclear decay is said to be random and spontaneous, but how do we know for certain, that it is not just a lack of understanding of some other unknown force?
Doesn't everything in the universe just depend on the starting conditions, so arguably nothing is random?
 A: We don't know anything "for certain" but experimental evidence favors randomness over Newtonian deteminacy for quantum decay phenomena. All we can do is proceed on the basis of our best experimental data to build theoretical models that employ consistent mathematics. To do otherwise would be outside scientific boundaries.
A: Let me focus on the first question that is posed: "Nuclear decay is said to be random and spontaneous, but how do we know for certain, that it is not just a lack of understanding of some other unknown force?"
I think the answer is: we do not know. The proof of this is that we have different interpretations of quantum theory, all of which are compatible with experiments, yet some have intrinsic randomness, whereas other are completely deterministic.
For instance, the de Broglie-Bohm interpretation (also known as pilot-wave theory) is a purely deterministic theory which reproduces all predictions of quantum theory. In this framework, the initial state entirely fixes when a nuclear decay will occur. However, it is exceedingly difficult to access the full information, and so it only seems random, just as how Newtonian physics can seem random when using statistical mechanics. (As a consequence, Born's rule is not an axiom in this framework but can be derived as a statistical fact, just like how in statistical mechanics you derive that a box of gas will be described by a homogeneous distribution in phase space.)
However, there is something we really do know: nature cannot be deterministic and local. Bell's theorem shows that any such theory of nature predicts a certain inequality which has been experimentally violated, concluding that a purely local and deterministic theory cannot be consistent with experimental fact. (E.g., the aforementioned pilot-wave theory is consistent with this, in that it has explicit nonlocal elements in it.)

A "don't shoot the messenger" disclaimer: For some reason, mentioning the existence of certain interpretations of quantum theory is offensive to some. I side with J.S. Bell in that it is useful to know what interpretations (compatible with experimental fact) exist, to clearly differentiate which things are forced upon us by nature, and which are merely a product of the choices we make. This has no bearings on what choices seem more 'minimal' or 'natural', which is quite personal and subjective.
A: Science doesn't tell us the reason things happen.  It provides a way to develop models which predict what will happen.  For all we know, Zeus himself personally causes every radioactive atom to decay when he sees fit.  Science cannot disprove such a claim.
What we can do is use the scientific method.  In the scientific method, we pick a "null hypothesis" which is what everybody expects to happen, and an "alternate hypothesis" which is the interesting thing we want to test.  Then we run an experiment and hopefully show that the null hypothesis is highly unlikely, while our alternate hypothesis is good.  In the case of this topic, the usual null hypothesis is "radioactive decay is random."
To date, nobody has been able to develop a test which can demonstrate that they can predict the timing of radioactive decays better than random chance.  That's not to say there's not some local hidden variable* or angelic cherub that knocks the atom about to cause it to decay.  It just says that nobody has been able to provide such a theory which does better than the "radioactive decay is truly random" theory does.
* Okay, I lie.  Moonman239 pointed out that Bell's theorem actually does state that you can't have local hidden variables.  Rather than editing it out, I keep it in with a footnote just because it shows just how weird our observations can be, and just how delightfully strange the universe must be.  Even very reasonable assumptions get tested and disproved on a regular basis!
A: 
Doesn't everything in the universe just depend on the starting conditions, arguably nothing is random. 

You are thinking in terms of classical deterministic physics which has been validated  in dimensions much larger than the quantum mechanical dimensions commensurate with Planck's constant h_bar. Nuclear decays are in the range where quantum mechanics has to be invoked, which is by construction a probabilistic theory. 
There are differential equations which give the solutions to quantum mechanical problems, where boundary conditions have to be imposed and the probability distributions are predicted and validated by the data. Individual measurements cannot be predicted , only the probability of finding a value can be predicted.
The randomness of the nuclear decays is due to this quantum mechanical  probabilistic underpinning:

A nucleus does not "age" with the passage of time. Thus, the probability of its breaking down does not increase with time, but stays constant no matter how long the nucleus has existed. 

P.S. For complicated quantum mechanical systems have a look at this answer of mine  
A: I broadly agree with existing answers at the time of writing. I hope I can add something helpful. I would like to underline the role of model-making in science. The physical world does what it does, and in science we construct models. The models help us build insight into the nature of the physical world. But the model is not the same as the physical world.
In the case of phenomena such as radioactive decay (and another good example is light reflecting off a partially reflecting surface) our most complete model is the one provided by quantum mechanics. In quantum mechanics the model includes randomness (let's not get into Everett interpretation here, it will not change the central point I want to make). So we think the decay is random because we think quantum mechanics is offering a good model. That is not the same as certain knowledge; it is a case of reasonable belief.
If someone wishes to propose another model, one in which the decay events are not random, then they are welcome to do so. It will be received if it matches experimental observations and has an elegant mathematical framework or other such beauties to recommend it. It will be enthusiastically celebrated if it also manages to predict something currently unknown or puzzling and get it right. But no one is currently able to think of a model like that.
By the way, personally I welcome a bit of openness or non-determinism in the world. If it is like that, as it seems to be, then it seems to me to be a more liberating sort of a world, and I say this even aware of all the pain that is also associated with random events.
