Dropping him from the relay team is the right call.
To the poster that said a coach's only job is getting the team to win, I hope your are a young teenager and not an adult. At the high school level, sports are about a lot more than winning. Even at the Olympic level, every athlete and coach do not have the goal of winning. For many it's getting a medal of any kind.
My concern in this situation stems from the following:
"I told him he had two strikes leading up until Penn and the next practice he missed he was DONE!"
This is the nuclear option. When the kids fails, and you almost know for sure that he's going to in a situation like this - kids don't change overnight, you will have lost the ability to work with him. This approach obviously didn't work with his prior sports. He was kicked off of those teams and he still F'd this up, too.
Last year we had a 1-in-20 year type sprinter miss several days at the beginning of the season. We have a points system for attendance. Once you exceed the limit you are done competing for the team. The athlete finished out the season running every practice, helping out at every meet, but he did not compete. It was a tough pill to swallow for all involved and a very visible reminder that team rules need to be followed. This year, the kid worked hard all winter and has been a sheer pleasure to work with in every aspect. If we had simply booted him from the team last year, I doubt he would be with us this year.
I love the quote that someone provided earlier in this thread that said something to the effect "don't establish any rule that you wouldn't apply to your best athlete at the worst possible time". Be firm, be consistent, etc. However, I think you should avoid consequences that remove the athlete from the coach's influence. It most cases the athlete isn't going to come back, and they are only going to remember that someone gave up on them. They aren't going to think about the situation in a mature rational fashion - if they had that capability they probably wouldn't have made the piss poor decisions they made earlier.
There are a wealth of consequences other than cutting a kid that can be used in most situations. They often take time and creativity to identify/implement, and so they are shunned for the easy out of cutting a kid.
FYC, I applaud your efforts and understand your frustations. Find a way to bring that kid back to you, if not the program. In the long run as a coach, how this relationship works out will be far more important that the race result at Penn.