From what I understand, (though don't quote me on this, I could be completely wrong) when freezing an app, it just renames the .APK. Thus, the app can't be run, but it's still there if you need it to be.
Completely removing it altogether removes all references to the app (or in this case, the references aren't even created to begin with) within the Android filesystem. It's cleaner, debatable whether or not it's "faster".
However, if you're concerned with receiving OTAs, then custom ROMs aren't for you, and sticking to freezing APKs is your best option. I've completely removed the ability to receive OTAs from the system (I think, since we have no OTAs to test with, unless I built on top of the original, 2.4.29, framework to try, I can't be 100% certain).