Okay, it looks like 5.1.9 made things better, but the deadlocks still happen sometimes. And you're right, it's not just with WAVs but with any supported stream format--I've now seen my engine lock up twice trying to play background music in Ogg format.
From my testing, it appears to happen more often on slower machines; my i3 and i7 laptops hardly ever experience the issue, but I can reproduce it much more easily on my cruddy AMD E2 desktop. Which, again, points to a race condition. Now that I have Allegro building on Windows, I might try to look into it myself, but then there's the issue of my not being able to reproduce it under the debugger...
Edit: Well, I found the source of the deadlocks anyway: al_destroy_audio_stream. I manually attached the debugger to a release build .exe (I had the .pdb for it) while it was locked up and it's stuck in an al_cond_wait.
Here's the function in my minisphere engine causing the lockup:
The reason this function exists is because, if you don't reload an audio stream after it plays through to completion, you can't play it again even if you manually seek to the start, as the feed thread has already terminated. So to get around this, I manually recreate the stream each time my engine's play_sound() function is called. This technique worked fine in 5.0, but apparently 5.1 doesn't seem to like it and deadlocks.