I've put off asking about this for a long time because it's not too major an issue for me, but I don't want it to be a problem for others when I distribute my game.

My game runs fine.
However...
When you start it from the quick-launch bar in Windows, most of the time al_install_audio will return false.
What is odd is you can right-click on the same icon and click the application icon in the context window and it succeeds 100% of the time.

Any advice on what I can do to make it work all the time?

    if(!al_install_audio())
    {
        al_show_native_message_box(nullptr, "Error!", "", "Failed to initialize audio.", nullptr, ALLEGRO_MESSAGEBOX_ERROR);
        return false;
    }

Which Windows, and which quick launch? Pinned to the start menu? Pinned to the task bar? Have you tried running the debug version Allegro in a debugger and seeing what part crashes?

Windows 7 64bit, pinned to taskbar.
I don't know how to debug Allegro, but I avoid a program crash by closing when the init fails (only from the taskbar with a left click)

That's interesting. My first thought was that the exe path might be different and some resource files are not loaded correctly.

However, you're saying the actual init fails. Have you tried a bare-bones program with only al_init and al_install_audio?

I can confirm experiencing the same problem on multiple machines with my games. I follow the same basic initialization pattern.