If you have to have one stored proc in the Utilities database, then you will need to go with dynamic sql. I'd also look at writing your procedures so that they don't use cursors unless absolutely necessary.

I'd also look at how you write your dynamic sql. If the differences are actually in the where clauses and the values passed to it, I'd look at use sp_executesql instead of execute(). sp_executesql can use cached plans where as execute() can't.