Can inserting new rows make the RDB not use an index? Say I have a table with 10000 records. I then delete them and create them again. This is done with "normal" sql, row by row (not some sort of bulk insert (BCP in sqlserver lingua)).

Does the RDB(Oracle in my case) still consider the indices on said table usable, or has it noticed many rows changed and stops using it?

(If the example above seems wierd here is a similar: Say I have a table with 10000 records with nice evenly divided data. I then insert 10000 new records with similarly evenly divided data.)
First, let me say that you haven't listed the version of your RDBMS, so I'm going to assume you're running a version that utilizes the Cost-Based Optimizer (CBO), as opposed to the Rule-Based Optimizer. The CBO was introduced in the 10g series of databases, so I think this is a safe assumption. If you're still running a 9i or earlier version, my answer won't help you.

So your question is "will inserts stop my RDB from using an index?". The easy answer here is no, they won't. Your database will continue to use the index it used before, as a_horse_with_no_name mentioned in the comments that the rows will be maintained automatically in the index without any extra effort from you. 

However, there is a chance that the volume of changes could impact the performance of using that index, which is something that you need to be aware of. How?

Take the total row count of all rows that could be included in an index (remember we cannot index nulls). Then consider the number of inserts you've done - is this number >= 10% of the existing rows? If the answer is yes, then your statistics are now considered out-of-date. Luckily, by default Oracle's later versions installs an overnight job (usually running around 10pm local server time) that will automatically gather statistics on any table &amp; indexes where it senses a 10% or greater change in the count of rows. 

But, if you are doing something outside of ordinary processing, say adding a significant amount of rows due to a one-time data load, you may very well need to gather stats yourself sooner than the automatic job. Also, in my experience, the automatic job only has a certain window of time in which to gather stats, so it's possible that it won't be able to gather stats on all objects if large amounts of data was manipulated across many objects. 

My point here is that changing data volumes significantly in a short period of time can lead to performance problems not because your indexes will be bad, but because in a Cost-Based world, the Optimizer will have bad information, and will make bad decisions.

I bring this up because you seem focused on indexes, which are only one tool in a much larger toolkit to having a well performing database.

HTH.