Thank you for your post.
If the "Delete Record" script is set to "Run script with full access privileges", then you should be able to delete the record. It could be something corrupt with the script or the layout. Try the following:
1. Create a new table "Test" with one text field "Name", and enter one record with Name: SmallTown
2. Create a new script "Delete Record" with the script step:
Delete Record/Request 
.... and be sure to check the option "Run script with full access privileges" at the bottom of the script dialog box.
3. Save the script and execute the script. You should get a warning "Permanently delete this ENTIRE record?". Click Cancel.
4. On the layout, create a rectangle, and with the rectangle still selected, pull down the Format menu and select "Button Setup..." Select "Perform Script" and select the script "Delete Record". Return to Browse Mode and save the Layout changes.
5. Click the button. You should get the warning "Permanently delete this ENTIRE record?" Click Cancel.
6. Assuming this file is being hosted, have the limited access user open this same file. Go to the layout and click the button. The user should get the same warning message. If not, then create another user account with a similar privilege set and access the file with this new account. Try deleting the record again. Does this work?
Any other information you can provide may be helpful in narrowing down the possible cause(s).
I was tripped up by this one just recently. The "run with full access privileges" is only "full access" for the current file. If your script attempts to modify a field or delete a record in a related file, that file's access privileges now apply. The solution is to create a delete script set to run with full access privileges in the data file and use a perform script in the layout file to run it.
Quoting from Filemaker Help:"The Run script with full access privileges feature only functions in the file in which the script is defined. This command will not override access restrictions on external files. For example, a script to delete records in File A that has the Run script with full access privileges option enabled will not delete records in an access-restricted external file File B."