The error has nothing to do with the use of a recovery catalog or not and whether the entries are expired from the control file. It is the error you would expect to encounter if you simply DROP a tablespace and then go into RMAN and issue a restore tablespace <tablespace_name>, which is what the OP is doing.
C:\>rman target /
Recovery Manager: Release 22.214.171.124.0 - Production
Copyright (c) 1995, 2002, Oracle Corporation. All rights reserved.
connected to target database: ORCL9 (DBID=3074164973)
RMAN> restore tablespace test_restore;
Starting restore at 11-AUG-06
using target database controlfile instead of recovery catalog
allocated channel: ORA_DISK_1
channel ORA_DISK_1: sid=9 devtype=DISK
RMAN-00569: =============== ERROR MESSAGE STACK FOLLOWS ===============
RMAN-03002: failure of restore command at 08/11/2006 08:19:12
RMAN-20202: tablespace not found in the recovery catalog
RMAN-06019: could not translate tablespace name "TEST_RESTORE"