I would recommend that you start off by doing a comprehensive read of the following two links:

http://www.sqlskills.com/blogs/kimberly/stored-procedure-parameters-giving-you-grief-in-a-multi-purpose-procedure/[/url]

http://www.sommarskog.se/dynamic_sql.html

Your nullable parameters are most likely a big part of the problem and this is a pattern that is routinely problemattic in the ways that you describe. I'd rebuild that procedure using the parameterized dynamic SQL execution by dynamically building the string to execute with parameterization and then calling it with sp_executesql, as shown in both of the above articles.