How crazy can I get?
I'm thinking using Wall of Stone to create the Castle, then Polymorph Any Object to turn it into an adamantine castle. The Stronghold Builder's Guide might offer advice on how to make it fly, but I'm too lazy to read it. So how about we abuse an item casting
Reverse Gravity to get it off the ground, and engines using Gust of Wind to provide propulsion?
Wall of Stone works. Poly Any Object doesn't: The spell has a volume of 100 cubic feet per caster level, which sounds like a lot, but when you consider that outer walls of a castle were typically 10 feet thick, then at 20th level you can affect a 10x 20 section of wall per casting. Add in that it can be dispelled. And, of course, the fact that it can't create Adamantine, or other intrinsically valuable material.
Because of the way the spell works, you can't affect a section of wall. You P.A.O an entire object, or nothing at all. Also, since the volume is in cubic feet, rather than a radius, feats like Widen Spell don't help.
Now Wall of Stone can be used cumulatively. At 20th level (you said you didn't want to go Epic), your wall is five inches thick and 20 5x5 sections in area. It attaches/embeds itself in surrounding stone, so you can glue layers together to make continuous surfaces.
Further you can shape it as you cast, so little details like murder holes, crenulations (the saw toothed look on the top of typical castle walls) and openings for doors and windows can be made, but that halves the volume of that casting.
Still, given enough time you should be able to build the fortress of your dreams.
Now, as for making the whole thing fly... You might consider enchanting it as a magic item, such as a Carpet of Flying. This is problematic though, since you wanted to avoid blind DM fiat. The castle far exceeds the weight limits of such an enchantment. There might be such rules in the Stronghold Builders guide, but straight item creation rules wouldn't cut it.
You could allw a *tiny* DM fiat by adding a spell like Overland Flight to the ones that can be grafted onto a Hallow spell. That spell makes an area or structure into a holy site, and lets you add one spell effect. The area is small (a 40 foot radius from casting point) but Widen Spell can help. Still small for an entire castle, but you're getting there.
That effect has to be renewed once a year, but that's not really an issue.
Want to make it really cool? Don't affix Overland Flight. Affix Wind Walk. The entire castle turns to vapor and flies at up to 60 mph, then re-materializes where you choose.
There are rules for crafting vehicles, such as ships that can sail over land, or that fly. Take a look at those, see if they lead anywhere.
Now if you just want it to float in one place, that's pretty easy: Fly to the appropriate location and use Force effects, like Wall of Force or Cube of Force, and make them permanent. (Some spells may not be on the normal list for Permanency, but Limited Wish can replicate the effect of that spell and bypass that limit. It has an Exp cost, but it always gets overridden by the cost of the Permanency itself: 500 Exp per spell level.)
Once you have a number of permanent force effects up in the sky, you bridge them with Wall of Stone or Wall of Iron to build the supporting undercarriage, expand to a stone foundation, and build your castle.
It's interesting to observe that many standard magic items, straight from the book, include abilities that can't be achieved with spells. For example, a Lyre of Building has an ability, once per day, that protects "all inanimate construction" within 300 feet from *ALL* damage. The protected walls, floors, whatever, are 100% indestructible for 30 minutes, and with a volume of a 600 foot diameter sphere it's just what the doctor ordered if you want your flying castle to survive that smash-landing you described. (It's possible to own several, so as to get longer periods of protection.)
Now comes the dirty trick: You want to stay strictly "by the book" in terms of spells, materials, etc. Custom spell research/design is in "the book". Reeks of DM fiat, I know, but it's there.