Probably enabling a search on a unique key of the table is the quickest way of deleting individual records.
Gmail do a good job of handling fairly random data sorting of emails.
If filtering isn't what you're after you need to be looking at scannability of your tables. So from a google search on 'Scannable tables' this post from Forrst comes top:

You should think about keeping the table header always visible so as they scroll down the table they don't get lost in the columns.
This section from Jacob Nielsen is for scanning a web page of text - but you need to apply the same principles to the data in your tables:
- Use meaningful rather than "cute" headings (i.e., reading a heading should tell the user what the page or section is about)
- Use highlighting and emphasis to make important words catch the user's eye. Colored text can also be used for emphasis, and hypertext anchors stand out by virtue of being blue and underlined
So highlight the columns of unique keys on the table so that users can search for those more easily.
You could also make it faster to select rows by allowing selecting anywhere in the row to highlight it for deleting and having a hover effect over the whole row to give a better indication that the whole row can be selected.