Once it's been deleted by you, it's been deleted. However I do believe Cydia remembers if a package was previously installed (just by simply watching what the command lines are saying when deleting in Packages tab in Cydia).
Besides that, I asked a similar question to yours and it is normal to see a prompt about the disk space issue. There is no issue and don't worry about it at all. You are fine. I like to delete directly from Sources tab in Cydia as I have found just one app (SpringJumps--vertical page flipping and it didn't work although it's updated) and I went to Cydia to delete and it worked fine.