For some SharePoint Online subscriptions, there appears to be a way to remove external users using the administration pages. But that is definitely not the case with SharePoint for Office 365 Enterprise. I found the solution.
First, connect to SharePoint Online using your trusty SharePoint 2013 Management Shell.
Next, search for the user using the "Get-SPOExternalUser" command. Unlike a lot of other "Get" commands, this one doesn't return a list of all of the things it's looking for. You must use a -Filter. Despite what the examples show in the documentation (as of this posting), your search filter for a user must match the first part of the first name, last name, or email address (as that page says at the top).
So to get the external user "John Doe
Then, you can use the "Remove-SPOExternalUser" command with the -UniqueIDs parameter and the user's UniqueID value to remove them.