The R garbage collector is imperfect in the following (not so) subtle way: it does not move objects (i.e., it does not compact memory) because of the way it interacts with C libraries. (Some other languages/implementations suffer from this too, but others, despite also having to interact with C, manage to have a compacting generational GC which does not suffer from this problem).
This means that if you take turns allocating small chunks of memory which are then discarded and larger chunks for more permanent objects (this is a common situation when doing string/regexp processing), then your memory becomes fragmented and the garbage collector can do nothing about it: the memory is released, but cannot be re-used because the free chunks are too short.
The only way to fix the problem is to save the objects you want, restart R, and reload the objects.
Since you are doing rm(list=ls()), i.e., you do not need any objects, you do not need to save and reload anything, so, in your case, the solution is precisely what you want to avoid – restarting R.
PS1. Garbage collection is a highly non-trivial topic. E.g., Ruby used 5 (!) different GC algorithms over 20 years. Java GC does not suck because Sun/Oracle and IBM spent many programmer-years on their respective implementations of the GC. On the other hand, R and Python have lousy GC – because no one bothered to invest the necessary man-years – and they are quite popular. That’s worse-is-better for you.
PS2. Related: R: running out of memory using `strsplit`