You are misusing character classes - an all too common mistake. See Michael's excellent blog entry at http://regexadvice.com/blogs/mash/archive/2008/01/31/A-touch-of-Character-Class.aspx. Consider the subpattern:
What this character class definition tells the regex engine is to match one or more characters that are not one of '(', ')', 'E','S', 'b', 'd', 'n', 'u' and the space character. This will match "#$%$#%" or "theBearwentoverthemoUntain" as these do not contain any of those characters. However "the bear went over the mountain" would not match because of the lower case 'b', the lower case 'u' and the space characters - actually you would get a match of "the". (This assumes the matches are case sensitive).
What you are wanting to do is to match anything that is not the string "End Sub". For that you need to use lookaheads in the following way:
What this does is to start at the current location within the text and see if the "End Sub" characters follow. If they don't (this is a negative lookahead) then match whatever the next character is (according to the 'singleline' or 'dot matches newline' option setting) which will also advance the current locaiotn within the text. If you are wanting to capture all of the characters matched by this pattern then you will need to insert it within a match group as in
Given the appropriate options settings, try:
^Sub((?!End Sub).)+End Sub$
This will return all of the characters beginning with a "Sub" that starts at the beginning of the text/line ('multiline' option) and grabs everything to the first "End Sub" as long as it is the last thing in the text/line.
Personally I think forcing the 'Sub' to be at the start of a line and the 'End Sub' to be at the end may be a bit restrictive in general as it does not allow for any text formatting or comments. Also I prefer to make these things case insensitive but I know that some language editors/compilers force the required case. As always, you need to understand the nature of the source you are examining.
As for why the performance is supposed to not be good, I would check that you have exactly the same situation. In general using the non-greedy '.*?xxx' pattern where you are looking to grab everything until you get to xxx works in basically the same way as the pattern I have provided above with the exception that the regex engine will try to make a match (not just a lookahead) with the 'xxx' part after it matches each character with the '.'. This means that the backtracking will amount to about as much work as my suggestion with the lookahead. If you have text such as:
sub end suc eeeend sub end sua end sub
then you will make the regex engine scan/match ahead for 6 characters because it can match the "end su" part before it finds a mismatch. In both cases you would then either reject the match or backtrack over all of those characters before you moved forward 1 character and tried again.
The subpattern '.*' can be very bad for performance and cause excessive bactracking (as well as finding the wrong terminating strings) in some situations. Also when you nest subpatterns within each other and use quantifiers, then you can get some very long match times if you are not careful.