By default Office SharePoint Server 2007 imports all profiles from the Active Directory Database. This presents an issue for some companies (mine in particular ;)). After doing some searching I found an older article by Michael Bollhoefer.
He tipped me off to the following LDAP filter which worked beautifully, and after running a full profile import and reindexing our SharePoint Search those old Inactive profiles were gone from the Database and the search.
(&(objectCategory=person)(objectClass=user)( !(userAccountControl:1.2.840.113556.1.4.803:=2)))
To set your LDAP filter go to Central Administration > SSP > User Profiles and Properties > View import connections. Edit your Connection and insert the User Filter as shown above. Click ok and run a full import.
Now you can switch over to your Microsoft SQL Server Management Studio and run the following query on your SharedServices Database:
select * from UserProfile_Full
where bDeleted = 1
You should see all of your Inactive users listed. Once the import is finished you can run the query again and you should return 0 results. The filter will also remove any rows from the dbo.UserProfileValue table as well.
Next, run a full crawl of your Local Office SharePoint Server sites to remove the old profile indexes from the My Sites and anywhere else in your SharePoint sites.