Hooray! I finally got it working. Gerhard, your comments about sorting and filtering put me on the right track. I was naively using a simple List as backing model. After looking closely at Trinidad's CollectionModel and understanding the concept of row keys I made my own collection model that simply uses a simple immutable counter on each row as a row key.
Adding/removing rows now works fine. Thanks again!