I assume every aircraft in the game has a unique id number in the database that is associated with a unique id number of a base airport for a player. The simplest solution would be to not associate the two until the aircraft is scheduled. Every airline would have an unscheduled aircraft "base" where all unscheduled aircraft would automatically get moved to. Once that first route is assigned, the base is assigned to the aircraft. If you remove the route, it goes back to your unscheduled aircraft base. This also solves the problem of doing fleet replacements when you are at the 100 aircraft limit at a base as you can do a one-for-one swap without having to rebase aircraft (let's admit it--the rebase function sucks and is a pain in the butt). On top of this, if you put in an order for 50 new aircraft, you don't have to worry about spreading them out across 4 bases and then playing musical aircraft when things change.
When you add route #1, base = origin. If route #2 origin != base, then give error message. When you remove a route, if schedule is empty then base = unscheduled.
The only other thing not included are the costs associated with rebasing an aircraft, which are always next to nothing--I say just get rid of it. The only place it would make a big difference is maybe Russia when you rebase an aircraft 3000+ nm away or if you are in the US and send an aircraft to Guam. Either way, it's not worth the hassle IMO.