I use RemoveIf very often, never had any problems.
I have 3 SP lists (each 20k+ records). I want to remove records from them. There are 1-20 rows for each criteria per SP list.

When I click a button, something is going on for a few seconds and then it is done. I get no errors, but records are still present in SP list. Criteria types are correct. This is not first time I used this command on these lists. Today it is not working.