It is quite intriguing that merely two evaluations of the polynomial suffice! Here is the trick: the coefficients of p(x) are exactly the coefficients used to represent the integer p(p(1) + 1) in base p(1) + 1. So Bob first asks for p(1), then ask for p(p(1) + 1) and writes p(p(1) + 1) in base p(1) + 1 to infer all coefficients of p(x).
For the second evaluation, any integer greater than p(1) + 1 would also suffice. For example, if p(1) were 6, then Bob could have chosen 10 for the second evaluation and read off coefficients of p(x) from the decimal representation of p(10).
References: Detailed explanation of the solution. On a Perplexing Polynomial Puzzle by Bettina Richmond in The College Mathematics Journal, Volume 41, Number 5, November 2010, pp. 400-403(4).