The initialization of LWJGL OpenAL fails sometimes, with no recognizable pattern. Sometimes it occurs multiple times successively, sometimes it does not. In most cases restarting the games helps.

The first try, where it did not work:
[18:02:44] [Client thread/INFO]: Setting user: XXX
[18:02:44] [Client thread/INFO]: (Session ID is token:YYY)
[18:02:46] [Client thread/INFO]: LWJGL Version: 2.9.1
[18:02:46] [Client thread/INFO]: Reloading ResourceManager: Default
[18:02:47] [Sound Library Loader/INFO]: Starting up SoundSystem...
[18:02:47] [Thread-6/INFO]: Initializing LWJGL OpenAL
[18:02:47] [Thread-6/INFO]: (The LWJGL binding of OpenAL. For more information, see http://www.lwjgl.org)
AL lib: (EE) MMDevApiOpenPlayback: Device init failed: 0x80004005
AL lib: (EE) MMDevApiOpenPlayback: Device init failed: 0x80004005
[18:02:47] [Thread-6/ERROR]: Error in class 'LibraryLWJGLOpenAL'
[18:02:47] [Thread-6/ERROR]: Unable to initialize OpenAL. Probable cause: OpenAL not supported.
[18:02:47] [Thread-6/WARN]: ERROR MESSAGE:
[18:02:47] [Thread-6/INFO]: Could not locate OpenAL library.
[18:02:47] [Thread-6/WARN]: STACK TRACE:
[18:02:47] [Thread-6/INFO]: org.lwjgl.openal.AL.create(AL.java:151)
[18:02:47] [Thread-6/INFO]: org.lwjgl.openal.AL.create(AL.java:102)
[18:02:47] [Thread-6/INFO]: org.lwjgl.openal.AL.create(AL.java:201)
[18:02:47] [Thread-6/INFO]: paulscode.sound.libraries.LibraryLWJGLOpenAL.init(LibraryLWJGLOpenAL.java:164)
[18:02:47] [Thread-6/INFO]: paulscode.sound.SoundSystem.CommandNewLibrary(SoundSystem.java:1576)
[18:02:47] [Thread-6/INFO]: paulscode.sound.SoundSystem.CommandQueue(SoundSystem.java:2572)
[18:02:47] [Thread-6/INFO]: paulscode.sound.CommandThread.run(CommandThread.java:121)
[18:02:47] [Sound Library Loader/WARN]: ERROR MESSAGE:
[18:02:47] [Sound Library Loader/INFO]: Could not locate OpenAL library.
[18:02:47] [Sound Library Loader/INFO]: Starting up SoundSystem...
[18:02:48] [Thread-8/INFO]: Switching to No Sound
[18:02:48] [Thread-8/INFO]: (Silent Mode)
[18:02:48] [Sound Library Loader/INFO]: Sound engine started
[18:02:48] [Client thread/INFO]: Created: 512x512 textures-atlas
[18:03:00] [Client thread/INFO]: Stopping!
[18:03:00] [Client thread/INFO]: SoundSystem shutting down...
[18:03:00] [Client thread/WARN]: Author: Paul Lamb, www.paulscode.com
Java HotSpot(TM) Client VM warning: Using incremental CMS is deprecated and will likely be removed in a future release

Closed the game and restarted it immediately (without closing the launcher or doing anything else):
[18:03:33] [Client thread/INFO]: Setting user: XXX
[18:03:34] [Client thread/INFO]: (Session ID is token:YYY)
[18:03:36] [Client thread/INFO]: LWJGL Version: 2.9.1
[18:03:36] [Client thread/INFO]: Reloading ResourceManager: Default
[18:03:36] [Sound Library Loader/INFO]: Starting up SoundSystem...
[18:03:37] [Thread-6/INFO]: Initializing LWJGL OpenAL
[18:03:37] [Thread-6/INFO]: (The LWJGL binding of OpenAL. For more information, see http://www.lwjgl.org)
[18:03:37] [Thread-6/INFO]: OpenAL initialized.
[18:03:37] [Sound Library Loader/INFO]: Sound engine started
[18:03:38] [Client thread/INFO]: Created: 512x512 textures-atlas

This happens in like 30% of the starts.

I already deleted the whole .minecraft user directory, but the error still occurs regularly.