The beats are audible at lower frequencies because your ears do in fact pick up phase information, but only at these lower frequencies.
When a sound enters our ear, we magnify it via mechanical oscillations of bones and hydraulic effects, ultimately causing vibration in a thin film in our inner ear called the basilar membrane. Different sections of the basilar membrane will vibrate in response to different tones. The basilar membrane is connected to thousands of small hairs, themselves connected to mechanically-sensitive ion gates. Oscillations of these hair then trigger the ion gates. The ion gates send electrical impulses down neurons to our brains.
Empirically, it is observed that these nerve impulses almost always begin at the peak amplitude of a vibration of the basilar membrane. Thus, if our two ears receive sound with different phase, they will fire nerve impulses at different times, and our brains will have access to phase information.
An interesting demonstration of this was given by Lord Raleigh in 1907. He theorized that phase difference detection between the ears was a key component to our ability to localize sound. When Raleigh played two tuning forks that were slightly out of tune, so that the phase oscillated, his found that human perception of the location of the sound oscillated from the left to the right of the listener's head.
At high frequencies, we lose phase information. This is because of uncertainties in the exact time of arrival of a nerve impulse. A typical nerve impulse lasts several milliseconds, so above 1000 Hz the uncertainty in arrival time becomes comparable to the frequency itself, meaning we lose phase information. It turns out that we mostly lose the ability to localize sound in the range 1000 - 3000 Hz. Above 3000 Hz, different physiological mechanisms related to the "shadow" of your head allow us to localize sound again.
Reference:
http://en.wikipedia.org/wiki/Action_potential
The information about Rayleigh's experiment and firing at the peak of oscillations is from chapter 5 of "The Science of Sound" by Rossing, Wheeler, and Moore.
Best Answer
No, one cannot hear the actual beat frequency. For example, if both waves are ultrasonic and the difference in frequency is 440 Hz, you won't hear the A (unless some severe nonlinearities would come into play; edit: such nonlinear effects are at least 60 dB lower in sound pressure level).
When two ultrasonic waves are close in frequency, the amplitude goes up and down with the beat frequency. A microphone can show this on an oscilloscope. But the human ear does not hear the ultrasonic frequency. It is just silence varying in amplitude :)
(I know a physics textbook where this is wrong.)
Edit: in some cases the mind can perceive the pitch of a "missing fundamental". For example, when sine waves of 880 and 1320 Hz are played, the mind may perceive a tone of pitch A. This is a psychoacoustic phenomenon, exploited for example in the auditory illusion of an Escher's staircase.