You can absoultely hit both CS4 & CS5, Mac & PC -- we do! Hell, we used to hit CS3, CS4 and CS5 
Your problem with CS5 & CS4 is probably that you're using a suite version that is only available in CS5. When Adobe updates a suite, they still make the old version available, but the headers will always use the version that shipped with their Illustrator by default (makes sense). So, for example, the Art Suite might be version 14 in CS4 and 15 in CS5. If you use the CS5 headers, kArtSuiteVersion is 15, but 15 doesn't exist in CS4.
Its easy to see if that's the problem -- add a message if AcquireSuite fails and have it print out the suite & version that failed. If that's the case, you'll just need to look at the CS4 SDK and figure out what version it shipped with (likely one less than you requested!). If you're not using anything added in the CS5 version, just switch the types & version requested to the CS4 one and after a recompile, you should be fine. Of course, this may repeat for several suites
It might be faster to look at what suites you're requesting and then just check each one. A fast way is to look in the legacy folder -- if theres an AI140*.h version of your suite, that means it was updated in CS5, and you'll run into this problem.
As for the ADM, well, we had the same experience. That's why we switched to Qt. There are undoubtedly other cross-platform toolkits you could use, but that one will work (albeit with some work). The next version of Illustrator won't even have the ADM in it, so its definitely wise to avoid the ADM at this point.
I'm not too familliar with Flex, but I believe you can hit CS4 & CS5 with the same UI. I'm not the one to answer that unfortunately, as we don't use Flex. There's another thread from the last week that discussed the finer points of 3rd party vs Flash UI that you might find useful. It should be one or two down from this one in the thread list.
Good luck!