You could have junk blocking the airflow but it should still come out hot. A drop in airflow is normal, you're forcing more air over the heater core than around it and that produces a bit of resistance.

Since the only way to clean it is to open up the plenum, replace the core. Aftermarket cores are almost ALWAYS the wrong size. If you can afford it, an OEM core (buy online not at the dealer) is the way to go. You have to discharge the a/c to do this job.

Good luck.