Deleting multiple songs from new itunes playlist

iTunes defines the random order of the tracks when you first specify set "Shuffle". (This is so that the skip forward / backward buttons work in a reasonable manner.) If you never turn Shuffle on or off, that order is never changed. Just disable and then re-enable Shuffle to get a new random order of tracks.

For more detail, see Why isn't iTunes shuffle random?.

I've had the exact same problem. There's more and more AppleScript bugs in each version of OS X.

If you just want to delete all tracks on a playlist, single expressions like this don't seem to skip any tracks and they're also faster:

tell application "iTunes"
    delete tracks of playlist "untitled playlist"
end tell

If you only need to delete some tracks, something like this might work:

tell application "iTunes"
    repeat
        set tr to tracks of playlist "untitled playlist"
        if tr is {} then exit repeat
        repeat with t in tr
            delete t
        end repeat
    end repeat
end tell