just to check, when you deleted the playlists, did you choose the option to delete from library and computer?
it's possible that the playlists were cleared out of windows media player but not the physical files - perhaps windows media player re-found them when booted up subsequently?
an alternative would be to try physically deleting the playlists from the playlists folder under the music directory and rebuilding the library before running wmp again
if you're not certain how to rebuild ...
1. open services.msc from the start (windows orb, bottom left, then type services.msc in the search programs and files box)
2. locate windows media player network sharing service and select the option to stop the process
3. goto \user\appdata\local\microsoft\media player from within windows explorer (you will need to enable hidden files to access this)
4. delete all files beginning with localmls, also delete all files with a .wmdb extension
5. restart the windows media player network sharing device
6. restart windows media player and wait for the libraries to rebuild - this should build from whatever it physically finds within the specified folders (nb. if you have your audio and video files stored separately from the music and videos folders, you will need to ensure the locations are included
