1. There is a redundant condition check in your example.  Once we start building the WHERE clause, we've already passed the first check, which would have prevented our getting down to the second check.

IF @LastName <> '' AND @NameID <> 0
   ...
   RETURN
END
...
--Begin building WHERE clause
IF @LastName <> '' OR @NameID <> 0
...

2. As has already been mentioned, performance of a dynamic SP will be poorer than a static SP.  It would make more sense to generate the SP externally and then import them in a SQL stream, or to hook directly into SQL Server and do it programmatically.  There's been a lot of work done in the realm of code generation (heck, entire system generation) that could serve as a model for this.  As with most things, we trade performance for flexibilty and vice versa.

3. It should be noted that SQLServer2005 removes the 8000 character limit.  This alone should be worth the migration.

4. How does the following statement provide SQL injection attack protection?

SET @LastName = REPLACE (@LastName, '''', '''''')