RemoveCustomToolbarButton removes the button definition (not the button itself on the toolbar), leaving a "dangling" button on the toolbar. First remove the button from the toolbar(s), then delete the definition:

using (ToolbarManager tbMgr = lfclient.GetToolbarManager(ClientWindowType.Main))
{
    int customButtonId = -1;

    // Find the ID of the custom button
    for (int k = 0; k < tbMgr.GetCustomToolbarButtonCount(); k++)
    {
        CustomButtonInfo customButtonDefinition = tbMgr.GetCustomToolbarButton(k);
        if (customButtonDefinition.Description == "My_Button_Name")
            customButtonId = customButtonDefinition.Id;
    }

    // Remove the button from all toolbars
    int nToolbarCount = tbMgr.GetToolbarCount();
    for (int n = 0; n < nToolbarCount; n++)
    {
        string strToolbar = tbMgr.GetToolbarName(n);
        for (int j = 0; j < tbMgr.GetButtonCount(strToolbar); j++)
        {
            ToolbarButtonInfo buttonInfo = tbMgr.GetButtonInfo(strToolbar, j);
            if (buttonInfo.Id == customButtonId)
                tbMgr.RemoveButton(strToolbar, buttonInfo.Id);
        }
    }

    // Remove the custom button definition
    int i = 0;
    while (i < tbMgr.GetCustomToolbarButtonCount())
    {
        CustomButtonInfo btnInfo = tbMgr.GetCustomToolbarButton(i);
        if (btnInfo.Description == "My_Button_Name")
        {
            tbMgr.RemoveCustomToolbarButton(i);
        }
        else
        {
            i++;
        }
    }
}