|Do you know where your variables are?|
What should I do to maintain each of my goals: backward compatibility to 5.005x, readability, and performance?
My answer would be if your sole goal is to assure backward compatibility, then you've really got no other option than stick with coding practices that are accaptable in both newer and older versions of Perl. This means, unfortunately, you'll have to leave slice($array, $index, 1) alone ;).
If, on the other hand, you are not worried about backward compatibility, I consider it a wholesome pursuit to improve readability and performance of one's code. In this regard, do whichever thou art deems appropriate! Therefore, if you consider delete($ARRAY); as a 'cleaner' alternative to the use of splice(), stick with the former. Indeed, this is a matter of taste and pleasing the audience (whoever will come to look at your code etc.)
UPDATE: expanded on my initial thought...