Aladdin got exactly what he was looking for with all three wishes.
Let's start with the first wish, looking at it in its full context from the Genie's perspective.
You're a genie. You've just met your new master, a kid named Aladdin. Dirt-poor, judging from his clothes -- a real underdog. Sneaky and clever enough that he's tricked you into helping him escape for free, but you can't entirely blame him for you not paying attention, and he seems to have gracefully accepted that he won't be able to do that again. Good-natured enough that he was willing to ask what you would wish for, which nobody ever has, and offered to give it to you with his last wish. So on balance, you like this guy, enough to do right by him. So what does he want?
Aladdin: Well, there's this girl--
Genie: Eehhh! Wrong! I can't make anybody fall in love, remember?
Aladdin: Oh, but Genie. She's smart and fun and...
Genie: Pretty?
Aladdin: Beautiful! She's got these eyes that just... and this hair, wow... and her smile! Ahh... but, she's the princess. To even have a chance, I'd have to be... hey. Can you make me a prince?
He wants to be able to court this princess, and wants to be a prince to that end. Meaning for the purposes of this wish, a prince is someone who is recognized as a prince -- by the Sultan, by Agrabah, by Jasmine.
It's a facade, but a facade is exactly what Aladdin's looking for -- and of course, facades and hidden natures are all over the place in this movie. A piece of brass junk hiding one of the most powerful beings on Earth; a thieving street rat who proves to be a diamond in the rough; a respectable royal adviser hiding dark ambitions; a birdbrain of a parrot who's secretly as intelligent and devious as his master (and an expert in disguising his voice); a woman in rags hiding a sheltered princess hiding a strong will and quick wits. In the movie's very first scene, the merchant (who may well secretly be the Genie) says, "it is not what is outside, but what is inside that counts" -- and Jafar later confirms (while in disguise, naturally), "Things aren't always what they seem".
Aladdin doesn't get a kingdom to go with the parade and clothes and elephant because he's not looking for a kingdom. Could the Genie have taken that route? Sure he could've. In fact, at the end of the movie, he was probably planning to:
Aladdin: Genie, I wish for your freedom.
Genie: One bona fide prince pedigree, coming up! I -- what?
By this point, of course, the Sultan knows who Aladdin really is, so it's reasonable for the Genie to assume a little more work would be necessary to satisfy the Sultan and the law; some documents certifying lineage, maybe a little history-rewriting.
Still, that's not what Aladdin wanted when he made his wish. He wanted, and got, a facade. True, later on he becomes uncomfortable with that fact -- the knowledge that everything people love him for came out of a lamp -- and grows to fear Jasmine finding out about his actual life history. (Also the Sultan, but I get the sense Aladdin's more concerned about Jasmine's approval than the law's.) Even if he did have a kingdom somewhere, it arguably wouldn't matter to his arc -- he'd still know he wished his way into it, and be tormented by hiding that fact from Jasmine and Agrabah.
Now how about the second wish? Clearly, the Genie fudges things a little. Maaaaybe Aladdin was still just barely conscious enough to move his head. Maybe he still had the presence of mind to nod in response to the Genie's prompt. More likely, he had already passed out by that point.
Two things, though. One, Aladdin had clearly rubbed the lamp with intent to wish himself to safety. Two, neither he nor the Genie dispute that it was a legitimate wish. They both let the "official version" stand. The Genie pretty much had to interpret it as a nod -- now that he knows enough to not let Aladdin cheat, it seems he can't let Aladdin cheat -- and Al's not nearly enough of an asshole to try to rules-lawyer it.
The point of all this is, the system isn't a machine. The two of them are bound by the rules, true (though the Genie isn't blocked in the cave, when he legitimately fails to realize no wish has actually been made). But the Genie has discretion in how he interprets wishes. And if he and his master have a mutual understanding afterward that a wish was made and granted, it works out, even if it's essentially a fiction like the second wish.
The Genie even shows some of this discretion with Jafar's first wish. If he can give Aladdin a "bona fide prince pedigree", presumably he can change things around so that everyone remembers Jafar having been the Sultan. Instead, he does the bare minimum -- in this case, another facade (useless under the circumstances), dressing Jafar in the Sultan's clothes. All anyone has to do is refuse to respect his authority, as Jasmine demonstrates. Regrettably, "the most powerful sorcerer in the world" and "an all-powerful genie" have less wiggle room.
(In The Return of Jafar, the fact that genies have wiggle room is more clearly displayed... on the other hand, Jafar suggests that unlike our own Genie, he can give things that weren't at all wished for. Though Abis Mal suspects that those treasures will disappear after he frees Jafar, and he may be right -- "Friend Like Me" clearly shows that even our Genie can conjure phantasmal treasure for demonstration purposes.)
The third wish, of course, is unambiguous and undisputed.
