>My user will never delete more than 5% of records: they enter
>invoices, customers, goods and packing runs periodically, largest
>tables are 250000 records, 30 MB
>
>Do you agree that in this case index on deleted() will decrease the speed of queries?

No, I wouldn't say that...it just might not increase the speed much...
It's supposed to be more dependent on size than # of deleted's. I don't believe that's a large enough table for the deleted index to make a lot of difference in SQL, but were I you, I might test a little to compare the results, if you haven't done it yet...besides we're all curious about it, now :)