If you have auto update enabled, it sould delete the songs in the database afer you deleted them on your ipod with iTunes, manually or any program you like.
2nd) Yes you can make playlists with your pc, if you your program uses relative paths and you save them in the m3u-format.