This is what finally worked for us:
Grid.MouseDown += new MouseEventHandler(Grid_MouseDown);
Grid.MouseUp += new MouseEventHandler(Grid_MouseUp);
void Grid_MouseDown(object sender, MouseEventArgs e)
{
  if (e.Button != MouseButtons.Right)
    return;
  HitTestInfo ht = Grid.GetHitTestInfoAt(e.Location);
  if (ht.Row < 0)
    return;
  NodeBase rightClickNode = (GridNode)Grid.Rows.GetNodeFromRow(ht.Row);
  if (!rightClickNode.Selected)
  {
    foreach (NodeBase node in Grid.Rows.SelectedNodes)
      node.Selected = false;
  }
}
void Grid_MouseUp(object sender, MouseEventArgs e)
{
  if (e.Button != MouseButtons.Right)
    return;
  if (Grid.RightClickNode != null)
  {
    if (!Grid.RightClickNode.Selected)
      Grid.RightClickNode.Selected = true;
    ShowContextMenu();
  }
}