"test -n && echo not empty" prints "not empty". Is that expected behaviour?

Yes, this is expected behaviour. When only one argument is passed to test, a length check is performed. From man bash:

test and [ evaluate conditional expressions using a set of rules based on the number of arguments.

0 arguments: The expression is false.

1 argument: The expression is true if and only if the argument is not null.

That is, essentially it is the equivalent of test foo, but using -n as the string.

test -n is prima facie malformed, since -n requires an argument. I believe some historical implementations treated it as a syntax error (and returned a nonzero status). However, in all the shells you're likely to encounter in the 21st century, the behavior is well-defined (by POSIX, following existing practice): if test has only one argument, then it is true if and only if that argument is non-empty.

Note that if you leave out the quotes, the test may end up being false for some non-empty values of $VAR. It can even print out an error message if there are globbing characters in $VAR.

VAR='foo -a -z bar'; test -n $VAR || echo "true... and false is false"
VAR='= n-'; test -n $VAR || echo "this is an equality test"
VAR='*'; test -n $VAR || echo "you may or may not see this depending on what files are in the current directory"

test -z $VAR is similarly broken.

Ksh, bash and zsh have a [[ … ]] conditional construct which imitates the traditional test and [ utilities. Unlike [, which either is an external utility or is a built-in that is parsed like one, [[ … ]] is part of the shell syntax. There is no word splitting or globbing inside [[ … ]]. [[ -n $VAR ]] is fine (as long as you don't care that your scripts won't run under other shells such as ash).