Globally consistent natural evidence on past climate evolution is indispensable for climate model evaluations and forecasts. However, it has rarely been investigated quantitatively whether large sets of globally distributed pollen records with limited dating resolution can be statistically linked. This could facilitate the identification of global in contrast to regional climate change signals on millennial to orbital time scales. We consider a global set of time-irregular pollen records for a joint analysis of spatial similarity on different time scales during the last glacial. Making use of measures suitable for irregular time series and by application of a spatio-temporal stochastic model, we examine significant commonality between pollen records. We quantitatively assess the resulting paleo-climate networks while respecting the spatially heterogeneous and sparse proxy archive layout. The network configurations are compared to synthetic proxy networks, which mimic different real-world record impairments. We find strong commonalities of well resolved Chilean, North Pacific and European records on orbital to millennial time scales. They reveal partly inverted deglaciation signals for westward exposed coastal tree vegetation. Such signals are consistently observable for several mid-latitude records, probably indicating equatorward shifts of westerly circulation structures during the last glacial. Surrogate data suggests that a notable part of total records might be insufficiently resolved to detect statistically significant record similarity at least when classical correlation-based measures are utilised. We compare the results to temperature and precipitation signals in PMIP3 models.