How can it be that the beginning universe had a high temperature and a low entropy at the same time? The Big Bang theory assumes that our universe started from a very/infinitely dense and extremely/infinitely hot state. But on the other side, it is often claimed that our universe must have been started in a state with very low or even zero entropy. 
Now the third law of thermodynamic states that if the entropy of a system approaches a minimum, it's temperature approaches absolut zero.
So how can it be that the beginning universe had a high temperature and a low entropy at the same time? Wouldn't such a state be in contradiction to the third law of thermodynamics?
 A: Here is a case where I think most of the answers in the literature are not very good, because the correct answer was given in 1983 by Paul Davies, and rejected (this later article reviews the idea): Davies, Cosmological dissipative structure, International Journal of Theoretical Physics, September 1989, Volume 28, Issue 9, pp 1051-1066. Davies's explanation is obviously correct, and it is holographically consistent. It has been rediscovered by others since then, off and on, but it is not popular with Cosmologists, who do not like causal-patch descriptions of cosmology.
When you have an inflating universe, the maximum entropy state is the one which can fit in a deSitter horizon, which has a maximum entropy equal to the cosmological horizon area, which is miniscule. This means that an inflating universe is always low entropy, even in thermal equilibrium. Once inflation ends, the minscule entropy of the initial deSitter phase translates into low entropy initial conditions, smooth homogenous stuff filling the universe.
It is important to note that during inflation, the smooth homogenous stuff is the thermal equilibrium state inside a causal patch. The fluctuations are entirely equilibrated with a miniscule entropy. It is only at the end of inflation, when the cosmological horizon becomes big, that the specialness of the inflating condition is discovered.
The fundamental source of the time-asymmetry is then the expected value of the scalar inflaton field, whatever it is. When you produce a universe with a large value of a scalar producing a cosmological constant, you are starting it in what is effectively a zero entropy state.
A: This is a difficult question for many reasons. One reason is likely because most of the introductory thermodynamics textbook problems that we are familiar with from childhood do not involve gravity. 
To illustrate this difficulty with gravity consider, for example, this snippet from an article in the New York Times Review of Books by physicist/mathematician Freeman Dyson regarding the heat death of the universe:

The belief in a heat death was based on an idea that I call the
  cooking rule. The cooking rule says that a piece of steak gets warmer
  when we put it on a hot grill. More generally, the rule says that any
  object gets warmer when it gains energy, and gets cooler when it loses
  energy. Humans have been cooking steaks for thousands of years, and
  nobody ever saw a steak get colder while cooking on a fire. The
  cooking rule is true for objects small enough for us to handle. If the
  cooking rule is always true, then Lord Kelvin’s argument for the heat
  death is correct.
We now know that the cooking rule is not true for objects of
  astronomical size, for which gravitation is the dominant form of
  energy. The sun is a familiar example. As the sun loses energy by
  radiation, it becomes hotter and not cooler. Since the sun is made of
  compressible gas squeezed by its own gravitation, loss of energy
  causes it to become smaller and denser, and the compression causes it
  to become hotter. For almost all astronomical objects, gravitation
  dominates, and they have the same unexpected behavior. Gravitation
  reverses the usual relation between energy and temperature. In the
  domain of astronomy, when heat flows from hotter to cooler objects,
  the hot objects get hotter and the cool objects get cooler. As a
  result, temperature differences in the astronomical universe tend to
  increase rather than decrease as time goes on. There is no final state
  of uniform temperature, and there is no heat death. Gravitation gives
  us a universe hospitable to life. Information and order can continue
  to grow for billions of years in the future, as they have evidently
  grown in the past.

The point here is that, as a star loses energy via radiation, it actually increases in temperature. I.e., As it decreases in entropy (because $\delta S=\delta Q/T$) it actually increases in temperature! This is due to the gravitational attraction acting on the star and the fact that gravity is the most important contributor to the total energy of the star. This is a very unfamiliar situation, indeed.
I must also point out, however, that the total entropy of the star and the body being heated by the star will, actually, increase if the body being being heated is at a lower temperature than the star. The argument for this is standard. 
But, nevertheless, we see that a star can both decrease in entropy and increase in temperature. Thus, as a star dies, the star tends to a states of lowest entropy and highest temperature. Again, the star is not an isolated system, so the total system is still tending towards higher entropy. 
Additionally, this example is not exactly what you want because the direction of time in the example is opposite what you are looking for.
So, this answer, doesn't really answer your question. But I think it could be helpful to illustrate a counter-intuitive aspect of thermodynamic systems with gravity.
I don't know the full answer. It is apparently fairly complex and may or may not depend on cosmological inflation theory, about which I have long since forgotten everything I ever learned...
A: It's an example of adiabatic expansion. If you have a container full of gas and you expand the container, the gas cools. Entropy is preserved.
Adiabatic processes preserve entropy. Any decrease in entropy due to lowered energy, and correspondingly fewer possible velocities for the particles, is offset by an increase in entropy due to the expanding volume, and correspondingly increased possible positions for the particles.
The reason adiabatic expansion loses energy is due to energy being absorbed by the expanding container. It may seem confusing for this to apply to expanding spacetime, since you can't push on the universe and get it to absorb energy. My knowledge of general relativity is pretty much limited to what I found on Wikipedia, but as far as I can tell, the answer is that the universe totally does work that way. The stress-energy tensor, which controls the shape of the universe and how it changes, includes pressure. As far as I can understand, an object under pressure causes the universe to expand and the energy is absorbed by the gravitational field.
A: I had puzzled about that as well.  But while the temperature is high the mass/energy density is extremely uniform (as ilustrated by the uniformity of the cosmic microwave background radiation 380,000 years later in the evolution of the universe).  And gravity changes everything.  Uniform density is very low for systems dominated by gravity (in the relative sense that clumpy distributions have higher gravitational entropy).  So I think this is one way entropy is relatively low.
Another reason may be that the phase space of micro states grows as the universe expands.
A: Let me show you that there is no contradiction by pointing out e.g. that for ordinary expansion periods (that is away from first order phase transitions, decouplings...) the total entropy is actually constant in time while the universe is getting bigger and cooler. Or, going back in time,  the universe is getting hotter while S is kept constant. How is this adiabatic expansion possible? Well, the space is expanding but the space of particles' momenta is redshifting too, and the net result is a constant phase space volume. Since S measure this volume, the resulting entropy remains constant. 
A: The third law does not say that "if the entropy of a system approaches a minimum, it's temperature approaches absolut zero." It says that if the temperature approaches absolute zero, the entropy does. These are logical converses.
The second law of thermodynamics says that entropy can only increase, so if the early universe had been in a state of maximum entropy, then the cosmos would have experienced its heat death immediately after being born. This contradicts the observation that the present universe contains burning stars, heat engines, and life. These observations imply that the early universe was in a very low-entropy state, which shows that its initial conditions were extremely finely tuned. The reasons for this fine-tuning are not explained by general relativity or the standard model. Adding inflation to the model does not cure this fine-tuning problem.[Penrose 2005]
These ideas are strongly counterintuitive to most people, since we picture the early universe as an undifferentiated soup of hot gas, very much like what we might imagine a heat-dead universe to be like. In what way is the early universe not equilibrated?
We observe that the cosmic microwave background radiation's spectrum is a blackbody curve, which would normally be interpreted as evidence of thermal equilibrium. However, this observation only really tells us that the matter degrees of freedom were in thermal equilibrium. The gravitational degrees of freedom were not. In standard cosmological models, which are constructed to be as simple as possible, there are no gravitational waves. Although the real universe presumably does have gravitational waves in it, they are apparently very weak. In a maximum-entropy universe, the gravitational modes would be equilibrated with the matter degrees of freedom, and they would be very strong, as in models like Misner's mixmaster universe.[Misner 1969]
Even in Newtonian mechanics, gravitating systems violate most people's intuition about entropy. If we psssssht a bunch of helium atoms into a box through an inlet valve, they will quickly reach a maximum-entropy state in which their density is nearly constant everywhere. But in an imaginary Newtonian "box" full of gravitating particles, the maximum-entropy state is one in which the particles have all glommed onto each other in a single blob. This is because of the attractive nature of the gravitational force.
Charles W. Misner, "Mixmaster Universe", Physical Review Letters 22(1969)1071. http://astrophysics.fic.uni.lodz.pl/100yrs/pdf/07/036.pdf
Roger Penrose, 2005 talk at the Isaac Newton Institute, http://www.newton.ac.uk/webseminars/pg+ws/2005/gmr/gmrw04/1107/penrose/
A: Entropy is not the existence of heat or energy, but is more accurately described as the spread of energy. A universe with high heat and low matter density has very low entropy, the same way that a cup of hot water has low energy distribution when compared to a cold pool. If you throw the hot water into the cold pool the heat will spread throughout the pool as would be expected by the laws of thermodynamics, similarly the matter and energy from the big bang spread throughout the universe from a single point of low entropy.
A: It is perhaps best to look at the entropy of an extremely dense system in terms of information (think von Neumann entropy). Although we do not know how superdense and superenergetic matter quantizes exactly (we would need a theory of quantum gravity for that), it is clear that it must. As such, in this extreme state, particles have likely been squeezed into the lowest available quantum states (or rather are still in these states). These only correspond to high average energies per degree of freedom (and hence high temperature) because so many of the lowest ones are occupied that even so the occupied once have high energy. But informationally, we might know (almost) everything just by saying the lowest states are all occupied. That is a state of (almost) zero entropy.
A: The fundamental reason for the increase of entropy in the universe is the increase of the number of particles in the universe.
Because:
1: number of particles does increase, and that does increase entropy
2: I do not see a better explanation here
It may happen that entropy increases without increase of number of particles, for example when heat is convected from a hot object to a cool object, but there is a cool object because at some time particles where created. (the hot object is hot because it was wrapped into a aluminium foil, while the cool object radiated photon particles) 
A: Well, Entropy of a given system depends on the number of micro states available. This in turn depends on the variation of velocity of particles. At very high temperatures and due to gravitational effect I guess the probability of all the particles having a common velocity increases. Hence the no .of microstates available is quite small. Perhaps this is why it is said to have a low entropy in the beginning.
