You're exactly right: the listview is recycling views. You need some means of keeping track of which items have been "deleted" outside the control of the listview. In your case, it sounds like a simple array would do the trick.
Below is an example of code I've used to do the same thing. In this case, it's a checkbox, where all checkboxes are initially unchecked.
@Override
public View getView(int position, View convertView, ViewGroup parent) {
ViewHolder holder = null;
if (convertView == null) {
convertView = mInflater.inflate(R.layout.dialog_checkbox_item, null);
holder = new ViewHolder();
holder.checkbox = (CheckBox)convertView.findViewById(R.id.dialog_checkbox);
convertView.setTag(holder);
} else {
holder = (ViewHolder)convertView.getTag();
if (checkedArray[position] == true)
holder.checkbox.setChecked(true);
else
holder.checkbox.setChecked(false);
}
holder.checkbox.setText((CharSequence) mData.get(position));
return convertView;
}