Say I have process 1 and process 2. Both have a file descriptor corresponding to the integer 4.
In each process however the file descriptor 4 points to a totally different file in the Open File Table of the kernel:
How is that possible? Isn't a file descriptor supposed to be the index to a record in the Open File Table?
The file descriptor, i.e. the 4 in your example, is the index into the process-specific file descriptor table, not the open file table. The file descriptor entry itself contains an index to an entry in the kernel's global open file table, as well as file descriptor flags.
Each process has its own file descriptor table. File descriptor 4 in process 1234 points inside process 1234's table. File descriptor 4 in process 5678 points inside process 5678's table. A case you must be familiar with are file descriptors 0, 1 and 2 which for each process are the standard input, standard output and standard error, pointing wherever these were redirected to.
A process can open the same file more than once. This can happen coincidentally, for example when a process's standard output and standard error are redirected to the same terminal or to the same file. The underlying file table entries (e.g. Linux's struct file) carry more than information about the file; they also contain opening modes (e.g. read or write) and other state (such as flags, e.g. close-on-exec). For example, a process might have a terminal opened for reading only on file descriptor 0 and that same terminal opened for writing only on file descriptor 2. File tables entries also contain the process's position in the file; a process might want to lseek to two different positions in the same file, and so would use dup to obtain two handles to that file.
dup does an exactly what it says on the tin: both resulting descriptors point to the same file table entry and thus share the same offset. In order to get 2 different file table entries, I'm pretty sure you need to open the file twice.
Each process has it's own file descriptor table. That's all.
It's all very well described in UNIX Network Programming by Richard Stevens if you would like to learn it deeply.
Wouldn't an extra level of indirection fix your problem? ("All problems in computer programming can be solved by an extra level of indirection" - some wise greybeard). That is, the small integer in each process ends up as an index into a per-process array of kernel-space indexes into the "Open File Table".
For getting an intuition on why every file descriptor should be indexed on local file descriptor table, one can see the case of redirection in unix systems. For a process one can redirect its stdout to any other file and thus overloading the file descriptor "1" for that process without altering what that "1" meant for other process. Same holds true for stdin and stderr. Thus there must be a local file descriptor to support such behaviour.
4in both processes are relative to it's own number of open fd's. Fd's0-2(stdin,stdout,sdterr) are always opened for a new process and the numbers are not reserved for only that process.