Have you tried pulling up the toilet and seeing if there is an object stuck in thetrap (the S-shaped portion of the toilet drainage)? There is probably a better term than "S-shaped portion" but if you look at the toilet profile it will be apparent.
I had a similar issue and someone had dropped a toothbrush into the toilet, which got lodged sideways into the drain area. I took off the floor bolts, detached the water source, pulled up the toilet, looked up the toilet drain pipe, and the problem was immediately evident. You might need to buy a new wax ring to reinstall the toilet onto the floor.