I'm a little unclear about your database structure but what I would recommend, if you don't already, is to have a unique key for the table. Make it so every row in the DB table is uniquely identifiable by a number.
You would then use that number, and that number alone to delete the rows. It'd require a simplier query than your current one.
Sorry for some reason I missed the end of your post about your primary keys. I would still recommend a single numeric primary key. It makes identifying row a lot simplier for the checkbox method, as each value in the returned array contains all the information needed to remove a row.
So on the page that lists your records with the checkbox to delete each, you would give every checkbox the same name (in HTML) with square brackets. You'd also put the value for every checkbox to be the unique ID it has in the number base.
eg. you could run a select query and for each row returned by the query echo a checkbox with name="record" and value="$ID" (where $ID is the unique ID from the DB).
Then when the user hits the submit button the $record variable will be an array which will contain each unique ID that has been selected for deletion.
The non-selected checkboxes will not be in the array, it will contain only the IDs that were selected.
You'd then cycle through the array and run a delete query for every value in the array.
Here is sample code to generate your list of records to delete.
It uses field names called 'ID' and 'name' and makes a simple row with the name and checkbox for each.
Then when your user hits submit on the form that contains the output data from above you do something like this....
$result=mysql_query("SELECT ID, name FROM table");
$ID = $r["ID"];
$name = $r["name"];
echo "$name <input type='checkbox' name='record' value='$ID'/><br/>";
This would get the $record variable from $_POST, which is an array of all the IDs to be deleted. It would then run a loop through the array, copying the value in each position of the array to the variable $remove and run an sql query to delete that row of the database.
for($i=0; $i<count($record); $i++)
$remove = $record[$i];
mysql_query("DELETE FROM table WHERE ID='$remove'");
I hope that makes sense to you.