I have a ContextMenuStrip on a DataGridView with some action to perform on the selected record in the grid. My problem is that when the user right-clicks on a record, that record is not selected and he performs the action on an other record. The simple solution would be to be able to set that record on which the user has right-clicked. How do I do that?

All you need to do is handle the CellMouseDown event and if the right mouse button is down then manually set the current cell address:

dataGridView1.CurrentCell = 
  dataGridView1.Rows[ e.RowIndex ].Cells[ e.ColumnIndex ];