Googling for "smallest phone" gets some interesting results. The modu looks like the smallest (not smaller than a matchbox though) and is available locally. Alternatively, maybe one of those watch-phones?