I am afraid you didn't understand the algorithm of the padding oracle. I suggest study the algorithm given at Vaudenay's original article on this. He is very concise in what he writes in the article, but it is there.
It is deterministic, doesn't assume anything about plain bytes and works like this:
The last block of cipher text always has to contain correct padding bytes. If plain text was exact multiple of block size, last block would be a full padding block
Last block of cipher text then must be ending in one of these patterns:
n..nnnnn (n being block size)
Base on the above, the algorithm takes a cipher block from the cipher text (doesn't matter which one) to decrypt. It first prepends a random block in front of it, which pretends to be the previous cipher block. It then iterates the last byte of this block prepended and sends to Oracle until it receives a valid padding answer. This would take at most 256 tries.
At this point it is known that the prepended block xored with the decrypted cipher block resulted in a valid padded block, i.e one of those listed above. But we don't know which one. It is most likely a block of 1 padding (......1) but it is possible it could be any of those listed above.
To find which one it really is, algorithm starts modifying first the initial byte of the prepended block and send it to Oracle again. If it was a full padding block, by modifying the first byte of the prepended block we would have broken the padding. So if Oracle returns false padding, we know we had full padding block. If not algorithm changes the next byte and asks again and so on, until it receives from Oracle not valid padding answer.
This way we know exactly which one of those padding patterns we had, and so we know the last byte's plain value, which would be prepended cipher block's last byte x-ored by number of padding bytes. Actually if by good chance we had found a full padding byte, at this point we know all of the bytes of the block. But that is low probability. The chance that the padding was only 1 byte is the highest.
So the algorithm goes on to decrypting the whole block after decrypting the last byte, again by changing one byte's value at a time on the prepended block that pretends to be previous cipher block. It first tries to find a padding pattern of ....22 which decrypts 2nd byte from end, then looks for pattern ...333 which decrypts 3rd byte from end and so on. Each takes 256 tries max, so maximum it takes 256 * block size Oracle questions to decrypt a block.