Auctually thats how I've been removing them, using remove_entity most of the time, I switched to flags |= FL_KILLME as I figured it might have been a problem with the remove_entity function (and the fact I rarely seen it used in HLSDK)
The data that I free for the entity is a pointer to its class instance, which is all me. (ie, delete pEntityData[index]

Once thats deleted the entity can still exist but will be nothing but an info_target.
The thing is it doesnt seem to crash all the time, I went ahead and started making thousands of entities overnight and it wouldnt crash (50 ents a second with 2 second lifetime).