OK, walking you through this...
My guess on this one (without examining it) since the inside still works perfectly, it's not an alignment issue with your door due to humidity, house settling, etc... and that you had a little bit of dirt, dust, pollen, etc that was interfering with the outside lock cylinder... The graphite made the problem 10 times worse...
First off, get rid of the graphite... I mean take the can, and throw it in the garbage... Don't use graphite on locks, period... 99% of people, including the very few locksmiths still heck bent on using the evil stuff, use entirely too much by a factor of about 10000% (the appropriate amount is, rub a pencil lead over a key blank, insert into lock, repeat twice, I'm NOT kidding... any more than that and you're headed for trouble) and especially don't use it on a Medeco or other high security locks... It's just too easy to foul everything up, especially given the Medeco's pivoting pin design...
Secondly, you're gonna have to clean that stuff out of there... Get a good industrial grade cleaner/lubricant/protectant... I recommend Zep 45 NC or TriFlow from the hardware store... do NOT use cheap stuff like WD-40 or liquid wrench, as when mixed with graphite forms something the consistency of Elmer's white glue...
Third remove the lock from the door, again be warned, This is most likely going to be MESSY if you've been using graphite.. and I'll warn you ahead of time graphite stains just about EVERYTHING and tends to go EVERYWHERE (another reason not to use it)... put down a drop cloth first... If you get any graphite on light colored carpet, tile, or wood, do NOT touch it, use a vacuum hose attachment to suction it up WITHOUT rubbing it in (unless you like graphite stains that will NEVER come out)
Third, get plastic container large enough for the lock, a LOAD of paper towels and put on some clothes you don't care too much about... I'd wear gloves, as you should with any GOOD cleaner, but also because it't easier to remember not to touch anything if you have the gloves on.... Take it ALL outside...
Now, irrigate the cylinders with the cleaner, start with the keyway facing up (as if it were on your door, provided you're in the US) to flush out a good bit of what you've put in... once it stops running out dark, repeat with the keyway facing down (upside down if it were on your door, again, if you're in the US... if you're not, reverse that process as Americans mount their locks "upside down" according to Europe). From time to time, insert the key into the keyway, give it a jiggle, remove it and clean it with cleaner and wipe it off....
Once the cleaner starts running out clean, without much graphite in it wipe everything down and let the locks drain out as much as they will, wipe everything down again... Your key's will most likely work like new at this point... If so, once everything is drained out / cleaned up as much as it can be, reinstall them on your door.
Keep in mind, that cleaner, along with traces of graphite will STILL stick to your key every time you use it for several days... So don't plan on wearing anything light colored for a week or so... and be REAL careful to wipe off your key before putting it into your pocket.
Lastly, If that does NOT correct the issues, contact a Medeco authorized locksmith in your area to determine if there is some mechanical failure, worn keys, pins, springs, sidebar, etc... This is a rare possibility unless there is a MASSIVE amount of use on JUST one side (again, as your inside cylinder isn't having any issues)
Good luck,
Derek