I load right away (first load screen) and keep what objects/images are always used in each level/area in memory: UI, HUD, player, etc.
Durring level/area loads I use LUA scripts and object lists to help decide what objects from the last load can stay and which ones can be removed, as well as what new objects are needed. Often times I find I keep a lot of the same objects anyway.
You can also delay object removal to happen every so often or based on player location. I've been testing this with Ian Mold's (Matrix plugins) co-operative multi-threading (ie, not the multi-process kind of multi-threading) and ticker features. If you have a large list of things to kill and it would bog you down to do all at once, you can do it based on a list of visible or pertinent objects. Kill one thing every so often and you don't notice it... I think. I dunno if it's a solid practice, I'm a bit insane/masochistic so it works and makes perfect sense to me. I think it helps with the more "seamless/loading-less world" type situations.
Also, you may wanna profile the lag you get from deleting objects. Just try deleting a lot of things between a profile timer and see what happens. It may not be that bad in your case. Like so:
Sync On
t# = hitimer()
for i = 1 to 5000
Make Object Box i, 1, 1 ,1
Next
t1# = hitimer() - t#
t# = hitimer()
for i = 1 to 5000
delete Object i
Next
t2# = hitimer() -t#
do
cls
print t1#
print t2#
sync
loop
I get quicker delete times than make times on this one... then again I could be misinterpreting any given element of the practice here, I have no formal training. The help file merely states that you shouldn't use these (as well as making objects) constantly in the main loop but loading screen routines are fine and dandy. Most games have them. Also remember that your target audience is likely to have at least 1GB or more of RAM, that's still quite a bit these days unless you do not optimize your resources.