The best answer I've come up with so far tests 35 prisoners in the worst case. It uses a similar setup as previous answers, but instead of separating the 1000 bottles into 4 groups of 250, I separate them into 8 groups of 125. This reduces the number of prisoners needed to 35 from 39 (I'll explain how I calculate this at the end).
First, we separate the bottles into 8 groups of 125 each. We take 8 prisoners and have them drink from 7 out of the 8 groups (prisoner 1 drinks from all but group 1, etc.) After this (as stated in other answers, but I'll clarify if needed), we're down to two scenarios for day two.
Day Two - Scenario 1
In the first scenario, 2 of our original prisoners have lived. This means that 2 of the 8 groups of bottles each contained one poisoned bottle. We'll label these groups A and B, each with 125 bottles. Now we can set up a simple binary mapping with 7 prisoners per group:
Prisoner 1: 0000001 (1,3,5,7,etc.)
Prisoner 2: 0000010 (2,3,6,7,10,11,etc.)
Prisoner 3: 0000100 (8,9,10,11,12,13,etc.)
The figure above shows the "bit" that the prisoner would be assigned, and all of the corresponding bottles he would sample from. You would first set up two groups of 7 prisoners (prisoner A1, A2... B1, B2...). One group would drink every bottle from group A, then apply their binary mapping to group B. The other group of prisoners would do the opposite. After this, you perform a logical OR on the dead prisoners' assigned bits. For example, if prisoners A1, A6, B3, B4 and B7 died, then the bottles that were poisoned were A33 (0100001) and B76 (1001100).
After this, we tested 14 prisoners on day two, and lost 6 prisoners on day one (re-using the two survivors), for a total of 20 prisoners. This is the best case scenario.
Day Two - Scenario 2
In the second scenario, only 1 of our original prisoners has survived. This means that 1 of the 8 groups contains both poisoned bottles. This is far more difficult.
There are two steps to day two. The first step is a simple binary mapping with 7 prisoners, similar to how you would solve the original "poisoned bottle" problem (only one poisoned bottle). Assign each prisoner one of 7 "bits". This is done the same as day one, above. The deaths in these prisoners will tell you which bits of the poisoned bottles are both 1's between the two bottles. For example, say bottles 39 and 97 are poisoned. In binary, these bottles would be:
The 1st bit and the 6th bit (from the right) are both shared between these two bottles, which means that prisoner 1 and prisoner 6 will both die, as they are the only two who would have sampled both bottles.
Now that we have the bits that are the same between both bottles, we need the bits that are different. To do this, we take 21 additional prisoners. These prisoners aren't given one "bit" each, but two. Thus prisoner 1 will be mapped to 0000011, and will drink any bottle with a 1 in the first or second bit (1,2,3,5,6,7,9,etc.)
Prisoner 1: 0000011 (1,2,3,5,6,7,9,etc.)
Prisoner 2: 0000101 (1,3,4,5,6,7,9,etc.)
Prisoner 3: 0000110 (2,3,4,6,5,7,9,etc.)
There will be many prisoners that die from this batch. First, we need to discount all the prisoners that would have died with a repeating bit (as in step 1). These prisoners would have died regardless of what their second bit was. In our previous example (with bottles 39 and 97), these would be:
Prisoner 1: 0000011
Prisoner 2: 0000101
Prisoner 4: 0001001
Prisoner 7: 0010001
Prisoner 11: 0100001
Prisoner 12: 0100010
Prisoner 13: 0100100
Prisoner 14: 0101000
Prisoner 15: 0110000
Prisoner 16: 1000001
Prisoner 21: 1100000
We know which prisoners these would be because of step one. Since prisoners 1 and 6 died in step one, the 1st and 6th bits are repeats. Any prisoners in step two with these bits are ignored. The remaining dead prisoners from step two are considered. Using our example, the dead prisoners would be:
Prisoner 17: 1000010
Prisoner 18: 1000100
What this says is that one bottle has the 7th bit set and the other bottle has the 2nd bit set (from prisoner 17). We also know that one bottle has the 7th bit set and the other bottle has the 3rd bit set (from prisoner 18). The only combination that makes this true is to have:
Bottle A: 1000000
Bottle B: 0000110
When we combine these with our known repeating bits, we get:
Bottle A: 1100001 (97)
Bottle B: 0100111 (39)
Note that we're performing the tests for step one and step two simultaneously and just noting the results afterwards.
Also note, that I believe step one is necessary. I don't believe you can determine which are the repeating bits using only step two, but I'm still trying to prove my concept.
In total, we have used 20 prisoners in scenario one (6 dead from day one, 14 more tested on day two). In scenario two, we've used 35 prisoners (7 dead from day one, 7 more tested on day two step one, and 21 more tested for step two).
Note that we know we need 21 prisoners for step two because we're looking at combinations of 2 bits chosen out of 7, which is 7C2 = (7!)/((7-2)!2!). This is how I determined that dividing the original 1000 bottles into 8 groups was ideal. Other possible configurations:
4 groups of 250
First day: 3 dead Second day: 8 + 8C2 = 8 + 28 = 36 Total: 39
8 groups of 125
First day: 7 dead Second day: 7 + 7C2 = 7 + 21 = 28 Total: 35
16 groups of 62/63
First day: 15 dead Second day: 6 + 6C2 = 6 + 15 = 21 Total: 36