If nitrogen is so important (it's a constituent of both proteins and nucleic acids), why are animals still throwing them out, and needing to eat it again? Is it true that in almost a billion years of evolution, life still haven't found a way to recycle nitrogen inside the cells or inside the body of multi-cellular organisms? Why does this seem so hard to achieve? Or are there animals that don't need to excrete nitrogen compounds (like ammonia, urea and uric acid), and instead reuse them?
The premise of the question is incorrect. Mammalian organisms do recycle nitrogen. They only excrete excess nitrogen.
Ammonia from deamination of amino acids can be incorporated into glutamate and glutamine:
Transamination can then transfer the amino group from glutamate, for example, to other ketoacids for the synthesis of other amino acids.
The capacity for recycling nitrogen is presumably determined by requirement. If there is excess to requirement, then there is no evolutionary advantage in retaining the excess and instead a mechanism has evolved to neutralize it and then excrete it.
Addendum: Recycling, yes, but why not also storage?
Although nitrogen from the degradation of amino acids is recycled, the excess is excreted, rather than stored in some form. Why has no storage form (analogous to glycogen or triglyceride) evolved? I will consider this from two inter-related viewpoints.
Yes, nitrogen is important for the proteins required for growth and maintenance of organisms, but the effects of depravation are only seen in the long-term. Carbon is of more immediate importance, i.e. the supply of carbohydrates to provide energy. Indeed, in extreme starvation of mammals metabolism treats muscle protein as expendable, breaking it down for the carbon skeleton of the amino acids. Thus, the selective advantage the evolution of a nitrogen storage system might give to an organism is not so clear.
If there were a nitrogen storage system one needs to consider what form it might take. Obviously not as ammonia, because of its toxicity, but it could be condensed into a neutral form. However a small metabolite, such as glutamate (above), would disrupt the metabolic balance, and a dedicated small molecule such as urea would be excluded because of the effect on osmosis and general water balance. So we are thinking of a macromolecule — a conventional protein like ovalbumin (which may, in fact, be a storage protein), or some special ‘new’ branched protein. The trouble with this method of storing nitrogen is that involves tying up large amounts of carbon — a price, as I argued in 1, that the organism cannot afford to pay.
Short answer: This is because the most common form of nitrogen found in multicellular organisms (not incorporated into any other compound) i.e. ammonia is too toxic to be stored or recycled.
Background: Ammonia, the product of deamination of amino acids, is basic in nature ($NH_3~+~H_2O \rightarrow NH_4OH \rightleftharpoons NH_4^+ + OH^-$) and thus disturbs intracellular pH (Ohmori et al, 1986). Though the mechanisms through which ammonia exerts its toxic effects are not known, hyperammonemia is known to alter several amino acid pathways and neurotransmitter systems, cerebral energy metabolism, nitric oxide synthesis, oxidative stress and signal transduction pathways, leading to irreversible damage to the developing central nervous system: cortical atrophy, ventricular enlargement and demyelination; causing cognitive impairment, seizures and cerebral palsy (Braissant et al, 2013).
Talking about how it is produced (just for information, skip this part if you are aware of urea cycle): Amino acids are deaminated for storage since the carbon skeleton of these amino acids can be easily converted to glucose or fatty acids for storage. This reaction yields ammonia which, in liver, is converted to urea (via urea cycle) which is not only less toxic, but also requires lesser water for excretion. See this page for more information and the diagram below.
Talking about why it is not recycled, there has always been a constant supply of amino acids to organisms (through nitrogen fixation or food). Indeed, amino acids are deaminated for storage i.e. we already have more than enough of it. Also, storing urea is also not easy since it is toxic too (it is just less toxic than ammonia). And since these products are so much harmful, it seems difficult for an organism to evolve itself so that it can store toxins rather than just throwing it away so that it can later be ingested in a useful form (amino acids from plants or herbivores). Finally, evolution works as decent with modification, meaning if something is a better alternative of current situation, it is not necessary that organisms will evolve towards that (unless there is strong selection pressure for it). In short, evolving to recycle nitrogen is (most likely) just not worth it.
P.S. you might be interested in this question to know more about evolution. Another answer here talks about storing excess nitrogen by adding ammonia into amino acids, yielding glutamate and glutamine. However, this process can be used only to a limited extent due to limited amount of substrate ($\alpha$-keto glutaric acid and glutamate) in the body. Also, excess glutamine in the body can have many major and minor side effects like skin rash, vomiting, etc. (see here for full list). Also, excess glutamate has much more pronounced effects. Since glutamate is a neurotransmitter, its excess causes cellular damage. This is what makes it an excitotoxin (see this for more details). Apart from this, the substrate ($\alpha$-keto glutaric acid) is an intermediate of Krebs cycle and is important in many other cellular activities (see here for details). So, its deficiency (caused due to conversion into glutamate) can easily affect many crucial metabolic activities. Thus, though this process seems an effective way of recycling nitrogen, it has many side-effects and is not much reliable i.e. can only be seen as an immediate solution. This is why when glutamate and glutamine build up in body, they are converted back to $\alpha$-keto glutaric acid and glutamate and the ammonia released via urea cycle.