AA used to let people go negative, up to -500 miles.
I am not LH elite, but they seem to have / had a perk where people could go very, very negative (tens of thousands of miles). I think they actually demand people after a certain amount of time to settle their account.
Last month, I had negative net charges on my NW US Bank visa card. They said they would post negative miles that month. That would be another means of potentially getting a negative balance. It turns out they didn't; I assume I won't get miles posted until I earn back that quantity.