Sounds like what happen to my buddy, when we did his garage with "garage" floor paint. Lasted a month before it started to peel up.
When he decided to redo the floor it did make sort of a mess getting the old paint off. We had a pressure washer and sprayed the floor, used a good all purpose cleaner and a broom and got most of the old stuff off. Some of the paint stayed on the floor but we figured that if it didn't come off with a pressure washer then it probably was stuck good to the floor. After cleaning it we rinsed it good and let it dry for 1-1.5 days. We had a few fans and a dehumidifier in the garage. That is the key, let it dry all the way.
But the biggest thing is to get the right "paint" too.
We found at Home Depot this stuff RustOleum makes that is a 2 part product and you mix it. One part is the paint and the other is the Epoxy which makes it hard and stick to the floor. But again the floor need to be completely dry!!
I only realized that we need a epoxy based paint was when I use to lay tile with bro-in-law, we used epoxy grout a few times and that stuff would not come off anything after it dried.
It's been 2 years with cars in and out, working on vehicles, dragging creepers around and CT winters and the floor looks like we just did it.
Here is the link for RustOleum.
RustOleum.com
Good luck with it.
Any ??'s let me know! I'll be glad to help.