I stand corrected.
Most likely I mixed in some observations with Puppy-Linux.
My problem with having 5 UARTS usable was definitely not with CONFIG_SERIAL_8250_RUNTIME_UARTS or CONFIG_SERIAL_8250_NR_UARTS in the Kernel, and yes, boot code 8250.nr_uarts=5 does the trick.
@Rich: Thanks for pointing to the other thread. However the issue with CONFIG_SERIAL_8250_NR_UARTS=4 seems to be fixed, both the config files for 3.8.10 and 3.8.13 have CONFIG_SERIAL_8250_NR_UARTS=32, making boot code 8250.nr_uarts=n usable for up to 32 UARTS.
@tinypoodle: Seems your shot for the interrupt was in the right direction, however I am not trying to share interrupts, see below.
Summary:
Problem was using IRQ 9 for ttyS4 while the interrupt had already been grabbed by ACPI:
tc@box:~$ cat /proc/interrupts 
           CPU0       
  0:      75839    XT-PIC-XT-PIC    timer
  1:       1783    XT-PIC-XT-PIC    i8042
  2:          0    XT-PIC-XT-PIC    cascade
  4:         10    XT-PIC-XT-PIC  
  6:          2    XT-PIC-XT-PIC    floppy
  7:        693    XT-PIC-XT-PIC    ehci_hcd:usb1, ohci_hcd:usb2, eth0
  8:          0    XT-PIC-XT-PIC    rtc0
  9:          0    XT-PIC-XT-PIC    acpi
 12:      10189    XT-PIC-XT-PIC    i8042
 14:       1666    XT-PIC-XT-PIC    pata_amd
[...]
After adding boot code acpi=off (my board doesn't have ACPI anyway) IRQ 9 was no longer in use, and after boot I get this (IRQs for ttyS2 and ttyS3 are not correctly detected, ttyS4 is unsurprisingly not detected at all):
tc@box:~$ setserial -g /dev/ttyS*
/dev/ttyS0, UART: 16550A, Port: 0x03f8, IRQ: 4
/dev/ttyS1, UART: 16550A, Port: 0x02f8, IRQ: 3
/dev/ttyS2, UART: 16550A, Port: 0x03e8, IRQ: 4
/dev/ttyS3, UART: 16550A, Port: 0x02e8, IRQ: 3
/dev/ttyS4, UART: unknown, Port: 0x0000, IRQ: 0
ttyS2 and ttyS3 are easily fixed:
tc@box:~$ sudo setserial /dev/ttyS2 irq 10
tc@box:~$ sudo setserial /dev/ttyS3 irq 11
ttyS4 can be configured by setting uart and baud_base manually (baud_base is necessary because only ttyS0-3 get this as a default):
tc@box:~$ sudo setserial /dev/ttyS4 port 0x03a8 irq 9 uart 16550a baud_base 115200
=> And now I have 5 working UARTs:
tc@box:~$ setserial -g /dev/ttyS*
/dev/ttyS0, UART: 16550A, Port: 0x03f8, IRQ: 4
/dev/ttyS1, UART: 16550A, Port: 0x02f8, IRQ: 3
/dev/ttyS2, UART: 16550A, Port: 0x03e8, IRQ: 10
/dev/ttyS3, UART: 16550A, Port: 0x02e8, IRQ: 11
/dev/ttyS4, UART: 16550A, Port: 0x03a8, IRQ: 2
However I still need to get the kernel compiling business going because of UIO.