Here's why this happens. (Spoiler alert: I was doing something wrong.)
One of the first things you learn about PowerCLI is how to enable the cmdlets in the PowerShell ISE. You do this so you can take advantage of the native PowerShell scripting environment while working on your PowerCLI scripts. At first, you may just issue the command to add these cmdlets manually:
And with that, PowerCLI cmdlets are now available in the ISE. But you quickly learn that you need to issue this command each time you launch the ISE. So you discover PowerShell Profiles, and you learn that creating a profile allows you to load these cmdlets at the start of each ISE session automatically. Pretty sweet. You end up with something like this:
And it lives in your home directory at My Documents \ WindowsPowerShell. Each time you lauch ISE from the Start Menu, the script runs (you'll notice a status message in the lower left of your ISE screen that says "Running script / selection. Press Control+Break to stop." You're good to go.
But every once in a while, when you launch ISE from anywhere other than the Start Menu, you find that your PowerCLI cmdlets are nowhere to be found. That's the problem I ran into, and it turns out that we need to go back and read more about those PowerShell Profiles from earlier.
When you created your PowerShell profile, you may have not noticed that the profile was specific to your user account. That means that if you launch ISE with any other account, your profile will not load. If you want the same profile to apply to all ISE sessions on your machine, you need to create a different profile. The file itself is identical to the one you created before, but this file needs to be in a different location: C:\Windows\System32\WindowsPowerShell\v1.0. Just copy&paste your profile.ps1 from earlier into this location, and every ISE session on your machine will load the PowerCLI cmdlets for you.
Sure, that sounds great. But what was really going on here, dude?
As it turns out, this behavior (in which my profile ran sometimes but not always) was the result of me running the PowerCLI shell as my administrative user, while using my non-privileged account to log into my workstation. With PowerCLI running as someone else (or more specifically, not the account that I created a $profile for), my personal profile wasn't loaded when ISE was launched (since ISE inherited the credentials of the user associated with the PowerCLI process). The system-wide profile that I created fixed this problem, but I could have just copied my profile to the correct location in the profile path for my administrative account.
tl;dr - I am now slightly less stupid than I was this morning.