I think it is a bug in the YouTube API version 3. You should check if it is already reported as a bug and if not you can file it yourself here: https://code.google.com/p/gdata-issues/issues/list?q=label:API-YouTube
if you decide to file it as a bug you should mention a playlistID that shows the problem.
I have noticed it too. However, it does not bother me. In my case: Using API version 3. The response is missing one or more items. Missing playlist items always appear as DELETED on youtube.com It happens on some playlists but not all. The playlist is PUBLIC and contains only videos from other channels.