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;
    }

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)

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