We consider the Klein-Gordon operator on an $n$-dimensional asymptotically anti-de Sitter spacetime $(M,g)$ together with arbitrary boundary conditions encoded by a self-adjoint pseudodifferential operator on $\partial M$ of order up to $2$. Using techniques from $b$-calculus and a propagation of singularities theorem, we prove that there exist advanced and retarded fundamental solutions, characterizing in addition their structural and microlocal properties. We apply this result to the problem of constructing Hadamard two-point distributions. These are bi-distributions which are weak bi-solutions of the underlying equations of motion with a prescribed form of their wavefront set and whose anti-symmetric part is proportional to the difference between the advanced and the retarded fundamental solutions. In particular, under a suitable restriction of the class of admissible boundary conditions and setting to zero the mass, we prove their existence extending to the case under scrutiny a deformation argument which is typically used on globally hyperbolic spacetimes with empty boundary.