You want to talk about format-preserving encryption. One of the main motivations for FPE is the ability to encrypt messages which lie in a short space, with an output which is in the same space.
The ideal encryption model on a space of size $S$ (e.g. $S = 10000$ for four-digit PIN codes) is that the encryption systems implements a permutation chosen randomly and uniformly among the set of $S!$ possible permutations. Or at least that the cipher is indistinguishable from such a randomly chosen permutation.
An extreme security model is then the following: assume that the attacker is given a black box which implements the encryption (and decryption) algorithms. He can ask for the encryption or decryption of the almost complete code book, i.e. $S-2$ requests. The attacker gets to choose the contents of each request, adaptatively. So at that point, the attacker can simulate the complete encryption function, except for two input values: he knows the two inputs (let's call them $p_0$ and $p_1$) and the two corresponding outputs ($s_0$ and $s_1$), but he does not know whether $p_0$ encrypts to $s_0$ or to $s_1$. His goal is to predict the encryption of $p_0$ with probability substantially better than pure luck (i.e. $1/2$).
A commonly quoted solution for FPE is the Thorp shuffle. It is an unbalanced Feistel cipher, with enough rounds to make it secure. The good part of it is that it is possible to prove security while keeping the number of rounds low enough to be practical (say 100 rounds or so). The bad part is that it does not realize the extreme model explained above. You have to relax a bit the model, because a Feistel scheme always implements an even permutation; so if you know all the code book except the encryptions of $p_0$ and $p_1$, then you can decide whether $p_0$ goes to $s_0$ or $s_1$ with 100% success rate, because only one of the two choices leads to an even permutation. However, the relaxation is not a big deal: if you give to the attacker only $S-3$ requests, then you can have the best possible under these conditions (attacker cannot predict the mapping of the three remaining inputs, except that they will have to comply to the "even permutation" rule).
To reach the "ideal" model with $S-2$ requests, you have to do heavier thing, like generating the complete permutation in a big array (this is certainly doable with only 10000 entries; for bigger spaces, memory-conscious solutions exist, but the CPU price is quite high). For a practical solution, use the Thorp shuffle.
For verifying PIN codes, encryption is probably not the right tool anyway. Indeed, as you notice, the space of PIN codes is so small that there must be a locking mechanism somewhere, which blocks the attempt after three wrong tries. You cannot have that from cryptography alone. In fact, you will get locking by using dedicated hardware: either a smart card (the smart card is tamper-resistant and locks itself after three wrong PIN codes) or a remote server (that enforces the locking policy).
FPE is used to realize other features, e.g. serial numbers with verifiable validity: you define an 8-digit number which embeds a 5-digit counter value, and you want to have a tool which can verify whether a given sequence of 8 digits is one of the 100000 sequences that you have issued; but you don't want anybody else to be able to generate random "valid" sequences with success probability higher than 1/1000. Solution is to encode the 5-digit counter as 8 digits by appending three zeros, then encrypting the whole lot with FPE. To verify, decrypt, and see if the three zeros are there.
