Data structure for storing points and finding a predecessor of a point
What about first computing the skyline (a.k.a. maximal vectors, etc.) of all points, then maintain a data structure for orthogonal range reporting? 

The range you are interested in is the orthant with coordinates smaller in all dimensions below your query point. 

Actually what you are looking for is a dynamic orthogonal range reporting datastructure. But I add the skyline in case you want to prune the set $P$ first (this answers the part you wrote about 'forgetting' point $p$ if there is some $p'\leq p$).