Pseudointellectual is correct. Take a look at the following snippet from this nice resource (archived):
With a handful of exceptions, compounds created by the addition of a
prefix are not hyphenated:
anteroom, antisocial, binomial, biochemistry, coordinate,
counterclockwise, extraordinary, infrastructure, interrelated,
intramural, macroeconomics, metaphysical, microeconomics, midtown,
minibike, multicultural, neoromantic, nonviolent, overanxious,
postwar, preconference, pseudointellectual, reunify,
semiconductor, socioeconomic, subpar, supertanker, transatlantic,
unnatural, underdeveloped
Exceptions include
compounds in which the second element is capitalized or a number:
anti-Semitic, pre-1998, post-Freudian
compounds which need hyphens to avoid confusion
un-ionized (as distinguished from unionized), co-op
compounds in which a vowel would be repeated (especially to avoid
confusion)
co-op, semi-independent, anti-intellectual (but reestablish,
reedit)
compounds consisting of more than one word
non-English-speaking, pre-Civil War
compounds that would be difficult to read without a hyphen
pro-life, pro-choice, co-edited