No, they shouldn't still be on the nano. However, make sure that those songs aren't in more than one playlist. For example, if you had a "recently added playlist" set to sync with your nano in addition to the playlist that you deleted the songs from, the songs might still be there even if you delete them from one of the playlists.
How many playlists do you have set to sync with the nano? As an experiment you could make it just one and then check to make sure that songs you delete from it are actually removed from the nano.