How have you "deleted" them? If they are shown in iTunes then they are still part of the library, even if you've removed the underlying media files. To remove an audiobook properly from iTunes:
- Select Books > Audiobooks
- Select the audiobooks you want to delete
- Right-click > Delete or press the Delete key
- When prompted, confirm that you want to remove the selected items and that you want to move the files to the Recycle Bin (if you've previously deleted the media file(s) you won't get the second prompt)
Note that this works when you're viewing your library, not a playlist. In the latter case (assuming a regular playlist) Right-click > Delete or pressing the Delete key will remove items from the playlist but not from your library. To do both at once use SHIFT-Delete.