Was there ever a real distinction between the two? I always have the urge to use maybe for discussing state and perhaps for actions. I know this is only because perhaps (by hap) and happen (befall by hap) share a root, but at least it's logical. Am I totally misguided here?
The differences between perhaps and maybe are the following:
The meaning of maybe is possibly, perhaps. Except in set phrases, you can replace maybe with perhaps. As far as I know, there is not the distinction in the usage of the words you describe; both the words can be used with actions.
[The examples are taken from the NOAD]
I don't believe there's any discernable difference, and I can't think of a sentence where maybe and perhaps could be switched and change the meaning or sound awkward.
A search on WordNet shows both words are in the same Synset and aren't a member of any other Synset, if you take WordNet as being semi-authoritative…