The structure of contacts page is changing depending on arriving messages and contact list.

Again orientation of screen reader and magnifier users might be better.

Proposed structure:

1/ Incoming from people in contact list
list of known people with incoming messages

2/ incoming from people not in list
list of other people with incoming messages

3/ contact list
list of all people in contact list including the ones with incoming messages
(always visible - short notice if empty)

4/ search result list + search box at the top + reset search (the search string might be stored in session)
(always visible)
the list would be last so that user is not forced to scroll through it, reset and search button at the top.