Python 2, 128 119 105 bytes

def F(p):
 v=n=1
 for r in map(None,*p.split("\n")):A,B=map(r.count,"()");n+=B-A;v*=n<2>A+B
 return n*v>0

Did you know that you can map None in Python 2?

Explanation

We want to start by transposing the Prelude so that columns become rows. Usually we would do this with zip, but since zip truncates to the shortest row length and itertools.zip_longest is far too long for code-golf, it seems like there's no short way to do what we want...

Except for mapping None:

>>> print map(None,*[[1,2,3],[4],[5,6]])
[(1, 4, 5), (2, None, 6), (3, None, None)]

Unfortunately (or rather, fortunately for all non-golf purposes), this only works in Python 2.

As for n and v:

• n acts like a stack, counting 1 - <number of unmatched '(' remaining>. For every ( we see we subtract 1, and for every ) we see we add 1. Hence if n >= 2 at any point, then we've seen too many )s and the program is invalid. If n doesn't finish on 1, then we have at least one unmatched ( remaining.
• v checks validity, and starts at 1. If the program is ever invalid (n >= 2 or A+B >= 2), then v becomes 0 to mark invalidity.

Hence if the program is valid, then by the end we must have n = 1, v = 1. If the program is invalid, then by the end we must either have v = 0, or v = 1, n <= 0. Therefore validity can be succinctly expressed as n*v>0.

(Thanks to @feersum for a multitude of good suggestions which took off 14 bytes!)

Previous, more readable submission:

def F(p):
 p=map(None,*p.split("\n"));v=n=0
 for r in p:R=r.count;A=R("(");B=R(")");n+=A-B;v|=A+B>1or n<0
 return n<1>v

J, 64 bytes

Input is a string with a trailing newline. Output is 0 or 1.

(0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)

Example usage

   ]in=.'#(#)##',LF,'###',LF,'###(#)',LF
#(#)##
###
###(#)

   ((0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)) in
0

The method is the following

• cut input at newlines and put into a matrix ];.2
• map ( / ) / anything else into 1 / -1 / 0 1 _1 0{~[:'()'&i.]
• define an s=.+/@: adverb which added to a verb sums the verbs array output

• add values in columns ]s

  • check positive () balance in every prefix [:(0>])s)[:+/\]
  • check equal () balance in the whole list (i.e. in the last prefix) |@{:@]

• add abs(values) in columns and check every element for a max value of 1 (1<|s)s

• as all the previous checks yielded positive at failure we add them up and compare to 0 to get the validity of the input 0=]

J, 56 bytes

3 :'*/0<: ::0:(+/\*:b),-.|b=.+/+.^:_1]0|:''()''=/];.2 y'

That is an anonymous function accepting a string with a trailing newline and returning 0 or 1. Reading from right to left:

• ];.2 y, as in the other J submission, cuts the string y at all occurrences of its last character (which is why the input needs a trailing newline) and makes a rectangular matrix whose rows are the pieces, padded with spaces if necessary.

• '()'=/ compares every character in that matrix first with ( and then with ) returning a list of two 0-1 matrices.

• +.^:_1]0|: turns that list of two matrices into a single matrix of complex numbers. So far the program turns every ( in the input into a 1, every ) into i, and every other character into 0.

• b=.+/ assigns the sum of the rows of that complex matrix to b.

• -.|b makes a list of 1-|z| for every z in b. The condition that every column contain at most a single parenthesis translates to all these numbers 1-|z| being nonnegative.

• +/\*:b is the vector of running sums of the squares of the numbers in b. If every column does contain at most one parenthesis, the squares of the numbers in b are all 0, 1 or -1. The , concatenates this vector with the vector of 1-|z|'s.

• now all we need to do is test that the entries of our concatenated vector v are nonnegative reals numbers, this is almost */0<:v, except that that causes an error if some entries of v are not real, so we replace <: with <: ::0: which just returns 0 in case of error.