the watermark appears on 2 pages, the title and the first TOC. After some testing I think the TOC resets the page numbering. If I insert a blank page after the title, the page of the start of the TOC is still one.
\documentclass[12pt,runningheads]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,hyperref,array,xcolor,multicol,verbatim,mathpazo}
\usepackage[normalem]{ulem}
\usepackage[printwatermark]{xwatermark}
\usepackage{fullpage}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.arrows}
\usepackage{array}
\setlength{\skip\footins}{24pt}
\newwatermark[firstpage,color=red!50,angle=45,scale=3,xpos=0,ypos=0]{Vorabgabe}
\begin{document}
\setcounter{page}{1}
\title{XXXXX\\ XXX }
\author{XXXX, XXXXX, XXXXX}
\begin{titlepage}
\maketitle
\thispagestyle{empty}
\end{titlepage}
\tableofcontents
\section{XXXX}
\end{document}
\documentclass
etc., the relevant packages and\end{document}
to your post\begin{tableofcontents}\tableofcontents\end{tableofcontents}
really looks weirdtitlepage
andmaketitle
, cf. for instance this post.