Yes, I would make it my business to get the $4500 back from the bank, especially since you have a carbon copy that proves that the cheque was altered, and they cashed it anyway. In my experience with cheque fraud (I had around $700 stolen from my account by someone impersonating me and forging my signature), after the bank compared signatures and saw that the signature was not mine, they made me sign an affidavit saying that this is what happened, then they refunded the money and got the police involved themselves.
It “should” be returned, we did all the paperwork and talking to a more considerate banking official the other day. It’s not going to be an instant thing though, and she made that clear. Once it’s shown no fraud on our part, the fee’s accessed will be waived and the stolen monies will be returned, this according to her can take 10 business days or more. Personally I see no reason for it to take more than 1 day to check, look, reverse. And I think that in a case of someone they know it would take less.
This happens a lot more than I thought, it happens to a lot of people. One thing I didn’t know, but do now thanks to the banks security, is that people paying for something by check have had others receiving there check and making personal checks of there own with your routing/banking information on them. What happened to us is also very common, and it seriously makes me think that our “safe” old fashioned method of modern day paying, is just as bad if not worse than the new pay everything using the digital medium.
And on that note, we signed up for “online banking” after some emails back and forth with various dopers, I’ve found out a lot. Fraud, it seems is quickly refundable if you pay using methods other than checks.
I hope that someone reading this thread that was in the same mind set we where, investigates further and makes there transactions safer.
I was surprised, too, at how insecure cheques really are when I had money stolen from me. When I thought about it, it made sense - a cheque signed by me for rent gave a thief all the information he needs - my bank, my account number, my transit number, my address, and look at that, my signature. In a rental situation, they knew the exact day that I would have a certain amount in that account (they cleaned me out the day before rent was due, if I recall correctly), since I was a reliable payer.
I got REEEEEAL careful with using cheques for a while after that (I’ve gotten sloppier lately - I should tighten that up again, and not ever use them). Thanks for that reminder. 
I’ve heard of something called “check washing” which may well be what happened here. Basically the thieves get a check somehow (stolen from a mailbox or whatever) and use chemicals to remove the critical info (payee, amounts) and alter them.
http://www.ckfraud.org/washing.html
It’ll be VERY interesting to see if the payee on the check that was cashed matches the payee on the check that you mailed. I could try to be charitable and say maybe it was stolen before the true recipient got it… though their refusal to respond to you does not support that!