Well, the easiest way would be to use a foreach loop. Let's say you're returning a value for each record to the deletion script. This is a value that you already said is part of each record. (For example, a member number or a part number, something unique).
Then use this logic:
1. Connect to the database.
2. Using the foreach loop, go through the array of values,
3. At each value, use an sql statement in a PHP database function to delete the record that matched that value,
4. Go to the next value until all are deleted.
The problem might be with the form configuration, too. if you've named the check box field the same thing in each record, you might be only returning one record instead of an array of records or a list.
What you might consider is giving each record a hidden form value that equals the unique value of the record (like the number mentioned above). This will get returned with any post action and perhaps you can create the array that way.
One trick you might try: write a PHP script with one line:
<?php
phpinfo();
?>
Save it as a script and insert it (temporarily) as the action for your form. This will return a page with all the internal PHP and web server settings, including everything you return to the server in the POST array. This way, you can examine precisely what's going back and figure out what the issue is.