This sounds like it could be caused from a few factors.
1) Possible Google sandbox
2) Too few pages indexed. (do a site:query)
3) Too few inbound links
4) A lot of competition with better optimized sites.

Keep in mind, the MSN spider is much hungrier than Google or Yahoo's spider.

Hope this helps:-)

It really doesn't make sense to me why google would like www.domain.co.uk but not www.domain.co.uk/page.php. What WOULD make sense is Google not liking page.php?q=blah where the dynamic page has a query string attached. The reason for this is because each time you introduce a query string to a dynamic page, you are virtually creating a new page. For example, page.php?do=faq is different than page.php?do=email. As you add more query strings, such as page.php?do=faq&item=4, you are virtually creating an UNLIMITED number of pages. Simply enter random text as a parameter and you have yourself a completely different page. Google likes to steer clear of this because it is afraid of its spider (and limited resources) being caught in an infinite loop spidering an infinite number of virtual pages on a site. For that reason, when it comes across dynamic URL query strings, it tends to be very stingy in how many it spiders, careful not to get itself indexing the same pages in triplicate or worse.

Here is an example: Suppose there is a php page called page.php which accepts the ?x= parameter and has the following php code on the page:
[php]
$next = $_REQUEST['x'] + 1;
echo "<a href=\"page.php?x=$next\">Next Page</a>";
[/php]

Basically, whatever number you enter into the query string, the page shows a link to one number higher. if you go to the page page.php?x=1 it will show a link to page.php?x=2. Google follows this page and it shows a link to page.php?x=3 and so on and so forth into infinity. An infinite number of pages in one line of code and one php document. See why Google is nervous?

That used to be true. However, currently Google will and can crawl and index multiple parameters in any url. Although, if you are still concerned about the dynamic url issue, you can always use a URL rewrite.

Oh, I never meant to say that Google was not capable of crawling or indexing multiple parameters in any URL. What I meant to say was that Google is more hesitant to crawl URLs with lots of parameters than static html pages because of the possibility / probability that most dynamic sites are capable of delivering a mathematically infinite number of unique pages.